一、Acm字符串题型完全总结篇

内容纲要

ACM-字符串完全总结

注意

  1. 对于字符串问题,最好使用char []来存储,不要用string,否则可能会占用大量内存及减低速度
  2. strlen(char []),以及相似方法的复杂度均为O(n),尽量不要用在循环内

字符串结合STL的基本使用

  1. 流的使用

    //StringSteam 流的使用
    #include 
    #include 
    #include 
    using namespace std;
    
    int main(int argc, char** argv) {
        string line,str;
        while(getline(cin,line)){
            stringstream ss(line);
            while(ss >> str){
                cout << str << endl;
            }
        }
        return 0;
    }
  2. String的方法

    //迭代器
    string::iterator it;  //创建名为it的迭代器
    //反转
    reverse(s.begin(), s.end());
    s1.assign(s.rbegin(), s.rend());   //反转并赋给s1
    //大小写转换
    transform(s.begin(), s.end(), s.begin(),::toupper);
    transform(s.begin(), s.end(), s.begin(),::tolower);
    //类型转换
    string ->int : string s("123");
    int i = atoi(s.c_str());
    int -> string: int a;
    stringstream(s) >> a;
    //子串
    s.substr(int pos = 0,int n = npos) const;
    //插入
    s.insert(int p0,string s)    //在p0位置插入字符串s
    //更改
    s.assign(str); //直接
    s.assign(str,1,3);//如果str是”iamangel” 就是把”ama”赋给字符串
    s.assign(str,2,string::npos);//把字符串str从索引值2开始到结尾赋给s
    s.assign(“gaint”); //不说
    s.assign(“nico”,5);//把’n’ ‘I’ ‘c’ ‘o’ ‘\0’赋给字符串
    s.assign(5,’x’);//把五个x赋给字符串
    //删除
    s.erase(13);//从索引13开始往后全删除
    s.erase(7,5);//从索引7开始往后删5个
    iterator erase(iterator it);//删除it指向的字符,返回删除后迭代器的位置  
    iterator erase(iterator first, iterator last);
    //查找
    int find(char c, int pos = 0) const;//从pos开始查找字符c在当前字符串的位置
    int find(const char *s, int pos = 0) const;//从pos开始查找字符串s在当前串中的位置
    int find(const char *s, int pos, int n) const;//从pos开始查找字符串s中前n个字符在当前串中的位置
    int find(const string &s, int pos = 0) const;//从pos开始查找字符串s在当前串中的位置。
    //删除所有特定字符
    str.erase(std::remove(str.begin(), str.end(), 'a'), str.end());
    //删除所有重复字符:
    要求对象有序O(n+n),如果先排序O(nlogn+n+n)
    str.erase(unique(str.begin(),str.end(),str.end());

字符串Hash

字符串的hash是最简单也最常用的算法,通过某种hash函数将不同的字符串分别对应到不同的数字.进而配合其他数据结构或STL可以做到判重,统计,查询等操作(如 map.size() == m判断是否有重复)

最常用的BKDRHash函数

unsigned int BKDRHash(char *str)
{
    unsigned int seed = 131;
    unsigned int hash = 0;
    while ((*str))
    {
        hash = hash * seed + (*str++);
    }
    //消除溢出
    return (hash & 0x7FFFFFFF);
}

stringHash数据结构

struct StringHash{
    ull seed = 131,n,hash[100005],base[100005];
    void init(char *s,ull _len,ull _seed){
        //这样处理之后,对于s的所有子串都可以在o(1)的时间内求出Hash值
        n = _len; seed = _seed;
        base[0] = 1; hash[n] = 0;
        for(int i = 1;i < n;i++){
            base[i] = base[i-1] * seed;
        }
        for(int i = n-1;i >= 0;i--){
            hash[i] = hash[i+1] * seed + (s[i]-'a'+1);
        }
        return ;
    }
    //返回hash[s[i]~s[j]]即返回从i开始到j的子串的hash值
    ull get_hash(int i,int j){
        return hash[i] - hash[i+j]*base[j];
    }
};

字符串Hash例题

  1. 例题:Hdu4821
    题解
  2. 例题:hdu4080
    题解

KMP算法

n:字符串长度
m:模版串长度

kmp是一种字符串匹配的算法,普通的字符串匹配(暴力匹配)需要时间O(n*m)
kmp算法通过对模版串进行预处理(建立部分匹配表),可以让复杂度降低到O(n+m)

找到每个位置的后缀和第一个字母的前缀的最大公共长度

相关资料1

相关资料2

暴力匹配

//暴力匹配:时间复杂度O(n*m)
void violentMatch(char *s,char *p)
{
    int n = static_cast<int>(strlen(s));  //文本串长度
    int m = static_cast<int>(strlen(p));  //模式串长度
    int i = 0,j = 0,cnt = 0;
    while(i < n){
        if(s[i] == p[j]){
            i++;
            j++;
            if(j == m){
                cnt++;
                printf("violentMatch find %d match in sign %d\n",cnt,i-j);
            }
        }else{
            i = i-j+1;
            j = 0;
        }
    }
}

KMP匹配算法

C++代码实现

//获取部分匹配表并 (右移 << ) 一位
void getPMT(char *p,int *f)
{
    int m = static_cast<int>(strlen(p));
    f[0] = f[1] = 0;    //f[0]肯定为0,f[1] = 0是由于右移
    for(int i = 1; i < m; ++i){
        //判断j的起点
        int j = f[i];
        //向前回溯,直到 无公共长度 或 再次找到部分匹配
        while(j && p[i] != p[j]) j = f[j];
        f[i + 1] = (p[i] == p[j]) ? j+1 : 0;
    }
}
//kmp算法,时间复杂度O(n+m)
void kmp(char *s,char *p,int *f)
{
    getPMT(p,f);
    int n = static_cast<int>(strlen(s));
    int m = static_cast<int>(strlen(p));
    int j = 0,cnt = 0;  //cnt计匹配数
    for(int i = 0;i < n;i++){
        //向前回溯,直到 无公共长度 或 再次找到部分匹配
        while(j && s[i] != p[j]) j = f[j];
        if(s[i] == p[j]) j++;
        if(j == m){     //找到匹配
            cnt++;
            printf("KMP find %d match in sign %d\n",cnt,i-m+1);
            j = f[j];   //回溯,查找是否有更多匹配
        }
    }
}

Python代码实现

def getPMT(p,f):
    m = len(p)
    f[0] = f[1] = 0
    for i in range(1,m):
        j = f[i]
        while(j and p[i] != p[j]):
            j = f[j]
        f[i+1] = j+1 if p[i] == p[j] else 0

def kmp(s,p,f):
    getPMT(p,f)
    n,m = len(s),len(p)
    j,cnt = 0,0
    for i in range(0,n):
        while(j and s[i] != p[j]):
            j = f[j]
        if(s[i] == p[j]):
            j += 1
        if(j == m):
            cnt += 1
            j = f[j]
    return cnt
if __name__ == "__main__":
    s = "ttttt"
    p = "tt"
    f = [0 for i in range(5)]
    ret = kmp(s,p,f)
    print(ret)

KMP例题

  1. 例题:Hdu1686
  2. 例题:Zoj3587

字典树

字典树参考资料

字典树数据结构

C++字典树指针实现

//字典树指针实现
struct trieTree_p{
    //成员变量:子节点数组,必要时可以用map
    int tot,root,child[maxn][letter];
    bool flag[maxn];
    //构造函数,以1为起点
    trieTree_p()
    {
        memset(child[1],0,sizeof(child[1]));
        flag[1]=true;
        root = tot = 1;
    }
    void insert(const char *s)
    {
        int *cur = &root;
        for(const char*p = s; *p; p++){
            cur = &child[*cur][*p-'a'];
            if(!*cur){  //如果没有该节点,创建
                *cur = ++tot;   //child[][] = 新建节点序号tot
                memset(child[tot],0,sizeof(child[tot]));    //初始化子节点值为0(表示空)
                flag[tot] = false;  //非终止节点,标记flag
                printf("new create char %c\n",*p);
            }
        }
        flag[*cur] = true;  //遍历结束,标记终止节点
    }

    bool query(char *s)
    {
        int n = static_cast<int>(strlen(s));
        int *cur = &root;
        for(char i = 0; i < n; ++i){
            cur = &child[*cur][s[i]-'a'];
        }
        return (*cur) && flag[*cur];
    }
};

C++字典树数组实现

//字典树数组实现
struct trieTree{
    //成员变量:子节点数组,必要时可以用map
    int tot,pos,child[maxn][letter];
    bool flag[maxn];
    //构造函数
    trieTree()
    {
        memset(child[0],0,sizeof(child[0]));
        flag[1]=true;
        pos = 1;
    }
    int idx(char c){
        return c - 'a';
    }
    void insert(char *s)
    {
        int n = strlen(s);
        int tot = 0;
        //bool mark = false;
        for(int i = 0; i < n; ++i)
        {
            int c = idx(s[i]);
            if(!child[tot][c]){ //tot = 0,从0开始建trie树
                //mark = true;   //新节点说明该串开辟了新的位置,肯定不是之前某个串的前缀
                memset(child[pos],0,sizeof(child[pos]));
                flag[pos] = false;
                child[tot][c] = pos++;
                printf("new create char %c\n",s[i]);
            }
            tot = child[tot][c];    //找到下一个字符的位置
        }
        flag[tot] = true;
    }
    bool query(char *s)
    {
        int n = static_cast<int>(strlen(s));
        int tot = 0;
        for(char i = 0; i < n; ++i){
            int c = idx(s[i]);
            tot = child[tot][c]; //子节点
        }
        return tot && flag[tot];
    }
};

字典树例题

  1. 例题:Poj3630
  2. 例题:Poj3167

AC自动机

AC自动机数据结构

struct ACAutoMationTire{    //数值范围太大,可以在全局创建对象
    int trie[maxn_p][letter]; //字典树
    int f[maxn_p];     //失败时的回溯指针
    int end[maxn_p];    //记录终止的信息(模式串可能有重复,用int而不用bool)
    int root,tot;

    int newNode() //节点信息包括 当前节点序号 和 终止信息
    {
        //初始化孩子节点值
        forl(i,0,letter) trie[tot][i] = -1;
        //终止信息
        end[tot] = 0;   //0表示该节点不存在终止情况
        //返回节点序号
        return tot++;   //tot在return后+1,表明有效节点数(序号)+1
    }
    //创建新节点,初始化孩子为-1,表明未创建
    void init()
    {
        tot = 0;    //初始化节点序号(0...n)
        root = newNode();   //创建根节点 
    }
    void insertWords(char *s){
        int len = strlen(s);
        int now = root;
        forl(i,0,len){
            int c = s[i] - 'a';
            if(trie[now][c] == -1){ //创建新节点
                trie[now][c] = newNode();
            }
            now = trie[now][c];
        }
        end[now]++;
    }
    void build(){
        std::queue<int> q;
        f[root] = root;
        //首先对根节点进行一次BFS
        forl(i,0,letter){
            if(trie[root][i] == -1){
                //如果为无效节点,根据父节点继续查找
                trie[root][i] = root;
            }else{  //如果节点有效
                f[trie[root][i]] = root;
                q.push(trie[root][i]);
            }
        }
        while(!q.empty()){
            int now = q.front();
            q.pop();
            forl(i,0,letter){
                if(trie[now][i] == -1){
                    //无效节点,根据父节点继续查找
                    trie[now][i] = trie[f[now]][i];
                }else{
                    //有效节点,设定失败指针并加入队列继续搜索 
                    f[trie[now][i]] = trie[f[now]][i];
                    q.push(trie[now][i]); 
                }
            }
        }
    }
    int query(char* s){
        int len = strlen(s);
        int now = root,ans = 0;
        forl(i,0,len){    //遍历文本串
            int c = s[i] - 'a';
            now = trie[now][c];  //从s[i]点开始寻找
            //每一个s[i],
            for(int j = now; j; j = f[j]){
                //一直向下寻找,直到匹配失败(失败指针指向根)
                ans += end[j];      //遇到终止标记则ans++
                end[j] = 0;    //如果只需要匹配一次模式串,则设为false
            }
        }
        return ans;
    }
};

AC自动机例题

  1. 例题:Hdu2222

发表评论