字符串数据结构模板

Trie 树

字典树，用于存储和查询数量较大的字符串。

#include <iostream>
#include <cstdio>
#include <cstring>
#define maxn 500010
using namespace std;
char aa[51];

struct Trie {
    int sz;
    int ch[maxn][26];
    int val[maxn];
    Trie() { sz=1; memset(ch[0],0,sizeof(ch[0])); }
    int idx(char x) {return x-'a';}
    void insert(char *s) {
        int n=strlen(s);
        int u=0;
        for (int i=0; i<n;i++) {
            int c=idx(s[i]);
            if(!ch[u][c]) {
                memset(ch[sz],0,sizeof(ch[sz]));
                val[sz]=0;
                ch[u][c]=sz++;
            }
            u=ch[u][c];
        }
        val[u]=1;
    }
    void check(char *s) {
        int n=strlen(s);
        int u=0;
        for (int i=0;i<n;i++) {
            int c=idx(s[i]);    
            if(!ch[u][c]) { cout<<"WRONG
"; return;}
            u=ch[u][c];
        }
        if(val[u]==1) {cout<<"OK
"; val[u]++;}
        else if(val[u]>1) cout<<"REPEAT
";
        else cout<<"WRONG
";
        return;
    }
}trie;

int main() {
    int n;
    cin>>n;
    for (int i=1;i<=n;i++) {
        scanf("%s", aa);
        trie.insert(aa);
    } 
    cin>>n;
    for (int i=1;i<=n;i++) {
        scanf("%s", aa);
        trie.check(aa);
    } 
    return 0;
}

例题：洛谷P2580

KMP算法

支持单个模式串匹配。

思想：用自己匹配自己。核心是next数组。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
using namespace std;
string s1, s2;
int len1, len2;
int next[1001];

void NEXT_init(){
    for (int i=1;i<len2;i++) {
        int j=next[i-1];
        while (j && s2[j]!=s2[i])
            j=next[j-1];
        if(s2[i]==s2[j]) j++;
        next[i]=j;
    }
    return ;
}

void kmp() {
    int j=0;
    for (int i=0;i<len1;i++) {
        while(j && s1[i]!=s2[j])
            j=next[j-1];
        if (s1[i]==s2[j]) 
             j++;
        if(j==len2) 
            cout<<i-j+2<<endl;
    }
    return ;
}

int main() {
    cin>>s1>>s2;
    len1=s1.length();
    len2=s2.length();
    NEXT_init(); 
    kmp();
    for (int i=0; i<len2; i++)
        cout<<next[i]<<" ";
    return 0;
} 

例题：洛谷P3375

AC自动机

支持多模式串匹配。

思想：Trie树+KMP算法；也可以看做模式串有多个的KMP算法在Trie树上的实现。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
const int maxn 50010
int tot, n;
char s[50];

struct Trie {
    int sz;
    int ch[maxn][26];
    int val[maxn];
    int f[maxn];
    Trie() { sz=1; memset(ch[0],0,sizeof(ch[0]));}
    int idx(char x) { return x-'a'; }
    
    void insert(char *s) {
        int u=0, n=strlen(n);
        for (int i=0;i<n;i++) {
            int c=idx(s[i]);
            if (!ch[u][c]) {
                memset(ch[sz],0,sizeof(ch[sz]));
                val[sz]=0;
                ch[u][c]=sz++;
            }
            u=ch[u][c];
        }
        val[u]=++tot;
        return ;
    }
    
    void getFail() {
        queue <int> q;
        f[0]=0;
        for (int i=0; i<26; i++) {
            int u=ch[0][i];
            if (u) {
                f[u]=0;
                q.push(u);
                last[u]=0;
            }
        }
        while (!q.empty()) {
            int r=q.front();
            q.pop();
            for (int i=0; i<26; i++) {
                int u=ch[r][i];
                if (!u) continue;
                q.push(u);
                int v=f[r];
                while(v && !ch[v][i]) v=f[v];
                f[u]=ch[v][i];
                last[u]=val[f[u]]? f[u]:last[f[u]];
            }
        }
        return ;
    }
    
    void find(char *t) {
        int n=strlen(t);
        int j=0;
        for (int i=0; i<n; i++) {
            int c=idx(t[i]);
            while (j && !ch[j][c]) j=f[j];
            j=ch[j][c];
            if (val[j]) print(i,j);
            else if(last[j]) print(i, last[j]); 
        }
        return ;
    }    
}trie;


void print(int i, int j) {
    if (j)
        printf("%d : %d", i, val[j]);
        print(i, last[j]);
    return ;
} 

Manacher

最长回文串的计算。

核心思想是把已经计算过的回文部分“抄过来”。

#include <iostream>
#include <cstdio>
#include <string>
using namespace std;

string a, a1;
int lena, p[100010];
int maxn=0;

int max(int x, int y) {return x>y?x:y;}
int min(int x, int y) {return x<y?x:y;}

void manacher() {
    int mx, id;
    mx=id=0;
    for (int i=1; i<=lena; i++) {
        if (mx>i) 
            p[i]=min(mx-i, p[id*2-i]);
        while (a[i+p[i]]==a[i-p[i]])
            p[i]++;
        if (mx<p[i]) {
            mx=i+p[i]; id=i;
        }
    }
    for (int i=1; i<=lena; i++) 
        maxn=max(maxn,p[i]);
    maxn--;
    return ;
}

int main() {
    cin>>a1;
    lena=a1.length();
    a+="$#";
    for (int i=0; i<lena; i++) {
        a+=a1[i];
        a+="#";
    }
    lena<<=1;
    manacher();
    cout<<maxn;
    return 0;
}

字符串Hash

不属于数据结构，但由于也与字符串有关，也放在这里。
使用BKDRHash和APHash

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

unsigned int BKDRHash(char *str) {  
    unsigned int seed = 31; // 31 131 1313 13131 131313 etc..  
    unsigned int hash = 0;  
    while (*str) 
        hash = hash*seed+(*str++);  
    return (hash & 0x7FFFFFFF);  
}  


int APhash1() { 
  int k(0), len = _str.length();
  for (int i = 0; i < len; ++i)
    k = ((_str[i] * (i + 1)) % INF + k) % INF;
  return k % INF;


unsigned int APHash2(char *str) {   //不是很懂的版本，求大佬讲解
    unsigned int hash = 0;  
    int i;     
    for (i=0; *str; i++)   
        if (!(i&1))
            hash^=((hash<<7)^(*str++)^(hash>>3));  
        else    
            hash^=(~((hash<<11)^(*str++)^(hash>>5)));
    return (hash&0x7FFFFFFF);  
}  

代码出处 BKDRHash & APHash1   APHash2