-s c++ != i++ sta out open pop 自动
题目链接:https://www.luogu.org/problemnew/show/P3808
- #include "bits/stdc++.h"
- using namespace std;
- typedef long long LL;
- const int MAX1=1e6+5,MAX2=5e5+5;
- int n;char s[MAX1];
- struct Aho{
- struct state{
- int next[27];
- int fail,cnt;
- }sst[MAX1];
- int size;
- queue <int> q;
- void init(){
- int i,j;
- while (!q.empty()) q.pop();
- for (i=0;i<MAX2;i++){
- memset(sst[i].next,0,sizeof(sst[i].next));
- sst[i].fail=sst[i].cnt=0;
- }
- size=0;
- }
- void insert(char *s){
- int i,j,ls=strlen(s);
- int now=0;char c;
- for (i=0;i<ls;i++){
- c=s[i];
- if (!sst[now].next[c-‘a‘]) sst[now].next[c-‘a‘]=++size;
- now=sst[now].next[c-‘a‘];
- }
- sst[now].cnt++;
- }
- void build(){
- int i,j;
- q.push(0);sst[0].fail=-1;
- while (!q.empty()){
- int u=q.front();q.pop();
- for (i=0;i<26;i++)
- if (sst[u].next[i]){
- if (u==0) sst[sst[u].next[i]].fail=0;
- else{
- int v=sst[u].fail;
- while (v!=-1){
- if (sst[v].next[i]){
- sst[sst[u].next[i]].fail=sst[v].next[i];
- break;
- }
- v=sst[v].fail;
- }
- if (v==-1) sst[sst[u].next[i]].fail=0;
- }
- q.push(sst[u].next[i]);
- }
- }
- }
- int get(int u){
- int an=0;
- while (u){
- an+=sst[u].cnt;
- sst[u].cnt=0;
- u=sst[u].fail;
- }
- return an;
- }
- int match(char *s){
- int i,j,ls=strlen(s);
- int now=0,cnt=0;
- for (i=0;i<ls;i++){
- char c=s[i];
- if (sst[now].next[c-‘a‘]) now=sst[now].next[c-‘a‘];
- else{
- int p=sst[now].fail;
- while (p!=-1 && sst[p].next[c-‘a‘]==0) p=sst[p].fail;
- if (p==-1) now=0;
- else now=sst[p].next[c-‘a‘];
- }
- if (sst[now].cnt)
- cnt+=get(now);
- }
- return cnt;
- }
- }aho;
- int main(){
- freopen ("aho.in","r",stdin);freopen ("aho.out","w",stdout);
- int i,j;
- aho.init();
- scanf("%d\n",&n);
- for (i=1;i<=n;i++){
- scanf("%s",s);
- aho.insert(s);
- }
- aho.build();
- scanf("%s",s);
- printf("%d",aho.match(s));
- return 0;
- }
[模板系列] AC自动姬
来源: http://www.bubuko.com/infodetail-2383874.html