题解 P3796 【【模板】AC自动机（加强版）】

Accoty_AM · 2019-06-13 19:23:59 · 题解

这篇题解主要说一下如何找出现次数

因为这道题没有说是否有重复子串，所以可能一个节点里有多个相同子串。虽然字串可能是唯一的，但也算是一种思路扩展吧。

如果只是单纯标记一个节点看这组数据

2

aba

aba

ababa

0

就会输出 2 aba

然而我们要 2 aba aba，这就需要特殊处理。。。

于是我们每个节点开一个vector

vector<int> sum[100000];

在处理到结尾的时候加入vector

void insert(char *s,int st){
    int len=strlen(s);
    int p=0;
    for(int c,k=0;k<len;++k){
        c=s[k]-'a';
        if(!trie[p][c]) trie[p][c]=++tot;
        p=trie[p][c];
    }
    sum[p].push_back(st);//这里加入
}

在计数的时候加上vector里的值

void ask(char *s){
    int len=strlen(s);
    int p=0;
    can[0]=-1;
    for(int k=0;k<len;++k){
        p=trie[p][s[k]-'a'];
        for(int i=p;i&&can[i]!=-1;i=fail[i]){
            for(vector<int>::iterator it=sum[i].begin();it!=sum[i].end();++it)
                ++total[*it].val;//这里计数
        }
    }
}

完整代码

#include<bits/stdc++.h>
using namespace std;
#define rg register
inline int read(){
    rg char ch=getchar();
    rg int x=0,f=0;
    while(!isdigit(ch)) f|=(ch=='-'),ch=getchar();
    while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return f?-x:x;
}
int trie[100000][26],tot,mode[100000],fail[100000];
char have[155][75];
char s[1000010];
int n,r,l;
struct node{
    int id,val;
}total[155];
void insert(char *s,int st){
    int len=strlen(s);
    int p=0;
    for(int c,k=0;k<len;++k){
        c=s[k]-'a';
        if(!trie[p][c]) trie[p][c]=++tot;
        p=trie[p][c];
    }
    mode[p]=st;
}
void clear(){
    for(int i=0;i<=tot;++i)//这里防止tot很小一个一个加。
        for(int j=0;j<26;++j)
            trie[i][j]=0;
    for(int i=0;i<=tot;++i) fail[i]=0;
    memset(mode,0,sizeof mode);
    tot=0;
}
void getf(){
    queue<int> q;
    for(int i=0;i<26;++i)
        if(trie[0][i]) q.push(trie[0][i]);
    while(!q.empty()){
        int x=q.front();q.pop();
        for(int i=0;i<26;++i){
            if(trie[x][i]){
                fail[trie[x][i]]=trie[fail[x]][i];
                q.push(trie[x][i]);
            }else trie[x][i]=trie[fail[x]][i];
        }
    }
}
void ask(char *s){
    int len=strlen(s);
    int p=0;
    for(int k=0;k<len;++k){
        p=trie[p][s[k]-'a'];
        for(int i=p;i;i=fail[i]){
            ++total[mode[i]].val;
        }
    }
}
bool cmp(const node &a,const node &b){
    if(a.val==b.val) return a.id<b.id;
    return a.val<b.val;
}
int main(){
    cin>>n;
    while(n){
        clear();
        for(int i=1;i<=n;++i) scanf("%s",have[i]),insert(have[i],i),total[i].id=i,total[i].val=0;
        getf();
        scanf("%s",s);
        ask(s);
        sort(total+1,total+1+n,cmp);
        r=l=n;
        while(total[l].val==total[l-1].val) --l;
        printf("%d\n",total[n].val);
        for(int i=l;i<=r;++i) printf("%s\n",have[total[i].id]);
        cin>>n;
    }
    return 0;
}

time（O2）1476