目录

字典树

AC自动机

后缀数组

---

        在学习的过程中，不懂的可以先将功能代码作为API，首先懂得如何调用，懂得各个特定数组的定义，先会灵活使用即可。

字典树

        字典树，顾名思义，这里以26个小写字母为例。特别地，字典树的根节点，字符内容为空。而对于字典树上的每一个节点（包括根节点），都有26个孩子节点。

这里需要非常清楚 trie[cur][i] 数组的含义：代表编号为cur的节点的第i个孩子的节点。 

题目概述：

        给n个字符串s1...sn,  再给出一个字符串p，问s1...sn中，前缀为p的字符串有多少个？

// problem :  
 
#include 
using namespace std;
#define ll long long
typedef pair<int, int> PII;
#define pb push_back
 
char s[15];
int trie[1000010][26];
int val[1000010];
int sz = 0;
void insert(char s[]) {
    int size = strlen(s), cur = 0;
    for (int i = 0; i < size; ++i) {
        int v = s[i] - 'a';
        if (trie[cur][v] == 0)
            trie[cur][v] = ++sz;
        cur = trie[cur][v];
        val[cur]++;
    }
}
int query(char s[]) {
    int size = strlen(s), cur = 0;
    for (int i = 0; i < size; ++i) {
        int v = s[i] - 'a';
        if (trie[cur][v] == 0) return 0;
        cur = trie[cur][v];
    }
    return val[cur];
}
int main(){
    int n; scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%s", s);
        insert(s);
    }
    scanf("%s", s);
    printf("%d\n", query(s));
    return 0;
}

AC自动机

        KMP是单模式匹配文本算法，其中关键是nxt数组。核心思想是：最大限度地利用先前已经匹配的字符，从而避免无效字符的多次匹配。

        AC自动机是多模式匹配文本算法，其中的关键是fail数组，核心思想同KMP一样。将多个字符串构建成一颗字典树，在字典树上跑“KMP”， 其实AC自动机跟KMP没什么联系，只是思想上是差不多的。 

上图为  abcd、abd、bcd、cd四个字符串建立的字典树。

        比如文本串为abcf， 在匹配到abcd中的c之后，发现f不匹配，根据fail数组，我们将原本匹配的abc变化为“已经”匹配好的bc，从而对文本匹配的过程进行了加速。所以关键是fail数组如何去构建。该过程由BFS完成。

题目链接：Keywords Search Problem - 2222 (hdu)

题目概述：

        给出一个文本串和多个模式串，求该文本串中包含多少种模式串？

题目分析：

        求多少种，所以，在匹配完一个模式串之后，将对应的val值置为-1，如果下次遇到val = -1的点，就跳过。（不跳过也行，但就相当于没有一个很好的剪枝操作， 可能导致时间超限， 需要注意的是，memset在数组大的时候，也是一个很耗时的操作，没必要将所有的数组元素memset）

// problem :  
 
#include 
using namespace std;
#define ll long long
typedef pair<int, int> PII;
#define pb push_back
 
 
// AC自动机
const int N = 1001005;
int trie[N][26], val[N], fail[N], sz;
queue<int> q;
struct AC_Automaton {
    AC_Automaton() {
        sz = 0;
        memset(trie[0], 0, sizeof(trie[0]));
    }
    void node_clear(int x) {
        memset(trie[x], 0, sizeof(trie[x]));
        val[x] = fail[x] = 0;
    }
    void insert (char s[]) {
        int len = strlen(s + 1), cur = 0;
        for (int i = 1; i <= len; ++i) {
            int v = s[i] - 'a';
            if (!trie[cur][v]) {
                trie[cur][v] = ++sz;
                node_clear(sz);
            }
            cur = trie[cur][v];
        }
        val[cur]++;
    }
    void get_fail() {
        for (int i = 0; i < 26; ++i) if (trie[0][i]) {
            fail[trie[0][i]] = 0;
            q.push(trie[0][i]);
        }
        while (!q.empty()) {
            int cur = q.front(); q.pop();
            for (int i = 0; i < 26; ++i) {
                if (trie[cur][i]) fail[trie[cur][i]] = trie[fail[cur]][i], q.push(trie[cur][i]);
                else trie[cur][i] = trie[fail[cur]][i];
            }
        }
    }
 
    int query(char s[]) {
        int len = strlen(s + 1), cur = 0, ans = 0;
        for (int i = 1; i <= len; ++i) {
            cur = trie[cur][s[i] - 'a'];
            for (int t = cur; t && ~val[t]; t = fail[t]) {
                ans += val[t];
                val[t] = -1;
            }
        }
        return ans;
    }
};
// 读入
int n;
char s[N];
void solve() {
    scanf("%d", &n);
    AC_Automaton AC;
 
    for (int i = 1; i <= n; ++i) {
        scanf("%s", s + 1);
        AC.insert(s);
    }
    AC.get_fail();
    scanf("%s", s + 1);
    int ans = AC.query(s);
    printf("%d\n", ans);
}
 
int main(){
    int t; scanf("%d", &t);
    for (int i = 1; i <= t; ++i) {
        solve();
    }
 
    return 0;
}

后缀数组

以例子来介绍后缀数组。

例如有个字符串为ababc，则其后缀字符串为：

 abaca

   baca

     aca

       ca

         a

将后缀字符串按字典序从小到大进行排序后，得到：

a

abaca

aca

baca

ca

后缀数组中，两个至关重要的是 sa数组，以及height数组。还有一个数组结构为rnk数组

sa[i] ： 字典序排名第i的后缀字符串是排序前的第sa[i]个字符串。

height[i] :  排序后的第i个字符串和第i - 1个字符串的最大匹配前缀是height[i] 

rnk[i] ： 与sa[i]相反，排序前的第i个字符串在排序后排名第几

由sa数组的定义可知，排序后的第i个字符串在初始串的下标，为sa[i]

以上述的例子为例，求出各数组的值：

i    排序前   排序后    sa     rnk    height

1   abaca    a              5       2          0

2     baca    abaca      1       4          1

3       aca    aca          3       3          1

4         ca    baca        2       5          0

5           a    ca            4       1          0

求sa、height、rnk数组的模板为：

const int N = 200005;
 
int wa[N],wb[N],wv[N],wss[N];
int cal[N], sa[N], rak[N], height[N];
int cmp(int *r,int a,int b,int l)
{return r[a]==r[b]&&r[a+l]==r[b+l];}
void get_sa(int *r,int *sa,int n,int M) {
    int i,j,p,*x=wa,*y=wb,*t;
    for(i=0;i0;
    for(i=0;i
    for(i=1;i-1];
    for(i=n-1;i>=0;i--) sa[--wss[x[i]]]=i;
    for(j=1,p=1;p2,M=p) {
        for(p=0,i=n-j;i
        for(i=0;iif(sa[i]>=j) y[p++]=sa[i]-j;
        for(i=0;i
        for(i=0;i0;
        for(i=0;i
        for(i=1;i-1];
        for(i=n-1;i>=0;i--) sa[--wss[wv[i]]]=y[i];
        for(t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1;i
        x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;
    }
    return;
}
void get_height(int *r,int *sa,int n) {
    int i,j,k=0;
    for(i=1;i<=n;i++) rak[sa[i]]=i;
    for(i=0;i
    for(k?k--:0,j=sa[rak[i]-1];r[i+k]==r[j+k];k++);
    for(int i=n;i;i--)rak[i]=rak[i-1],sa[i]++;
}
// 调用方法举例
while(~scanf("%s",s + 1)){
    n = strlen(s + 1);
    for (int i = 1; i <= n; i++) {
        cal[i] = s[i];
    } // 将s[i]数组转换为cal数组，如果全是小写字符，可以将字符集的范围缩小到26
    cal[n + 1] = 0;
    get_sa(cal + 1, sa, n + 1, 300); // 300 是ASCII码的范围
    get_height(cal + 1, sa, n);
 
}

题目链接：Problem - 1403 (hdu) Longest Common Substring

题目描述：

        求两个字符串S、P的最长公共子串的长度，（最长公共字符串也可以求出

题目分析：

        height数组表示相邻两个后缀字符串的最大前缀匹配数，所以，求最大的height即可。后缀数组求法，针对的是一个字符串，所以我们采用将两个字符串通过‘#’连接起来。注意在取最大的height时，相邻的两个后缀字符串必须一个是属于S的，一个是属于P的。

// problem :  
 
#include 
using namespace std;
#define ll long long
typedef pair<int, int> PII;
#define pb push_back
const int N = 200005;
 
int wa[N],wb[N],wv[N],wss[N];
int cal[N], sa[N], rak[N], height[N];
int cmp(int *r,int a,int b,int l)
{return r[a]==r[b]&&r[a+l]==r[b+l];}
void da(int *r,int *sa,int n,int M) {
    int i,j,p,*x=wa,*y=wb,*t;
    for(i=0;i0;
    for(i=0;i
    for(i=1;i-1];
    for(i=n-1;i>=0;i--) sa[--wss[x[i]]]=i;
    for(j=1,p=1;p2,M=p) {
        for(p=0,i=n-j;i
        for(i=0;iif(sa[i]>=j) y[p++]=sa[i]-j;
        for(i=0;i
        for(i=0;i0;
        for(i=0;i
        for(i=1;i-1];
        for(i=n-1;i>=0;i--) sa[--wss[wv[i]]]=y[i];
        for(t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1;i
        x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;
    }
    return;
}
void calheight(int *r,int *sa,int n) {
    int i,j,k=0;
    for(i=1;i<=n;i++) rak[sa[i]]=i;
    for(i=0;i
    for(k?k--:0,j=sa[rak[i]-1];r[i+k]==r[j+k];k++);
    for(int i=n;i;i--)rak[i]=rak[i-1],sa[i]++;
}
char s[N];
int n1, n;
int main(){
    while(~scanf("%s",s + 1)){
        n1 = strlen(s + 1);
        s[n1 + 1] = '$';
        scanf("%s", s + n1 + 2);
        n = strlen(s + 1);
        for (int i = 1; i <= n; i++) {
            cal[i] = s[i];
        }
        cal[n + 1] = 0;
 
        da(cal + 1, sa, n + 1, 300); // 300 是ASCII码的范围
        calheight(cal + 1, sa, n);
        int ans = 0;
        int pos = -1;
        for (int i = 2; i <= n; ++i) {
            if (height[i] > ans && 
                ((sa[i] < n1 && sa[i - 1] >= n1) || (sa[i - 1] < n1 && sa[i] >= n1)))
                ans = height[i], pos = sa[i];
        }
        printf("%d\n", ans);
        // 最长公共字符串
        for (int i = 1; i <= ans; ++i) {
            printf("%c", s[pos + i - 1]);
        }
        puts("");
    }
    return 0;
}