ZOJ 3228：Searching the String（AC自动机（两种不同的匹配方式所匹配出的结果））

数据结构

题面链接

• 题意

先给你一个不超过1000000长度的大串s；接下来输入一个n代表接下来输入的小串个数，小串长度不超过6。
小串分两种类型0和1类型。
0类型表示小串在大串中的最大匹配个数就是常规的AC自动机的做法。
1类型表示小串在大串中不能重合的最大匹配数。
依次输出结果.（所有的串只包含小写字母）
按样例输出，注意每组测试数据后有一个换行。

• 样例

Sample Input

ab
2
0 ab
1 ab

abababac
2
0 aba
1 aba

abcdefghijklmnopqrstuvwxyz
3
0 abc
1 def
1 jmn
Sample Output

Case 1
1
1

Case 2
3
2

Case 3
1
1
0

• 分析

当为0类型时就是最基本的AC自动机的解法。
当为1类型时我们就要用数组len[]来记录一下该节点位置单词的长度。用lastpoint[]来记录这个节点位置单词上次出现的位置。在循环大串的时候直接判断 i - len[j] >= lastpoint[j] 是否满足。如果满足说明没有出现覆盖上一次出现的位置，此时这种类型的ans就++。
说明一下。
对于每个小串我们在getfind函数里面都求出0，1两种类型情况下的结果。
用ans[maxn][0],来记录所有小串为0类型时结果。
用ans[maxn][1],来记录所有小串为1类型时结果。
注意！！！
很多小细节应该仔细一点。case的kk已经写错两次了！！！！

对于locate数组。locate数组存的是locate[i]表示第i个小串在树上的结尾节点。由于我们存的小串可能是相同的串，类型不同。如果还是照习惯用isword数组来存他是第几个串，那么相同的串的不同类型会被最后出现的串覆盖掉。所以先出现的小串则会出现找不到的情况。这样是不对的。

• 代码

#include<bits/stdc++.h>
using namespace std;
const int maxn = 6e5 + 6;
int last[maxn], f[maxn];
int ch[maxn][26];
int cnt;
int isword[maxn];//这个点是单词
int locate[maxn];//locate[i]表示第i个单词存在的节点位置
int lastpoint[maxn];//lastpoint[i]表示i这个节点处的单词上一次出现的位置
int len[maxn];//len[i]表示i这个节点处的单词的长度
void insert(char s[], int id)
{
    int root = 0;
    int l = strlen(s);
    for(int i = 0; i < l; i++)
    {
        if(ch[root][s[i] - 'a'] == 0)
            ch[root][s[i] - 'a'] = ++cnt;
        root = ch[root][s[i] - 'a'];
    }
    isword[root] = 1;
    len[root] = l;
    locate[id] = root;//这个单词处在树上节点的标号
    lastpoint[root] = -INT_MAX / 2;//由于单词长度不超过6 所以小于-7都OK
}
void getfail()
{
    queue<int>q;
    f[0] = 0;
    for(int i = 0; i < 26; i++)
    {
        int u = ch[0][i];
        if(u != 0)
        {
            f[u] = 0;
            q.push(u);
            last[u] = 0;
        }
    }
    while(!q.empty())
    {
        int r = q.front();
        q.pop();
        for(int c = 0; c < 26; c++)
        {
            int u = ch[r][c];
            if(u == 0)
            {
                ch[r][c] = ch[f[r]][c];
                continue;
            }
            q.push(u);
            int v = f[r];
            while(v && !ch[v][c])
                v = f[v];
            f[u] = ch[v][c];
            last[u] = isword[f[u]] ? f[u] : last[f[u]];
        }
    }
}
int ans[maxn][3];
void getfind(char T[])
{
    memset(ans, 0, sizeof(ans));
    int n = strlen(T);
    int j = 0;
    for(int i = 0; i < n; i++)
    {
        j = ch[j][T[i] - 'a'];
        if(isword[j])
        {
            ans[j][0]++;
            if(i - len[j] >= lastpoint[j])
            {
                ans[j][1]++;
                lastpoint[j] = i;
            }
        }
        int temp = last[j];
        while(temp)
        {
            ans[temp][0]++;
            if(i - len[temp] >= lastpoint[temp])
            {
                ans[temp][1]++;
                lastpoint[temp] = i;
            }
            temp = last[temp];
        }
    }
}
char s[maxn];
int type[maxn];
char s1[maxn];
int main()
{
    int kk = 0;//这种小细节不要再出问题了！！！！！！！！！
    while(~scanf("%s", s))
    {
        memset(ch, 0, sizeof(ch));
        memset(isword, 0, sizeof(isword));
        int n;
        cnt = 0;
        scanf("%d", &n);
        for(int i = 1; i <= n; i++)
        {
            scanf("%d%s", &type[i], s1);
            insert(s1, i);
        }
        getfail();
        getfind(s);
        printf("Case %d\n", ++kk);
        for(int i = 1; i <= n; i++)
        {
            printf("%d\n", ans[locate[i]][type[i]]);
        }
        puts("");
    }
    return 0;
}