AC自动机

cwy posted @ 2018年1月05日 16:36 in 板子 , 43 阅读

板子

http://192.168.45.99/problem.php?id=1623

#include<cstdio>
#include<cstring>
#include<iostream>
#include<stdlib.h>
#include<ctime>
#include<string>
#include<cmath>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<queue>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define LL long long
#define FOR(i,a,b) for (int i=a;i<=b;i++)
#define FORD(i,a,b) for (int i=a;i>=b;i--)
using namespace std;
typedef pair<int,int> pa;
void getint(int &v){
    char ch,fu=0;
    for(ch='*'; (ch<'0'||ch>'9')&&ch!='-'; ch=getchar());
    if(ch=='-') fu=1, ch=getchar();
    for(v=0; ch>='0'&&ch<='9'; ch=getchar()) v=v*10+ch-'0';
    if(fu) v=-v;
}
int cnt[500010],q[500010],fail[500010],n,m,x,son[500010][26],tot;
char s[500010];
LL ans;
void ins(){
    x=0;
    FOR(i,0,m-1){
        if (!son[x][s[i]-'a']) son[x][s[i]-'a']=++tot;
        x=son[x][s[i]-'a'];
    }
    cnt[x]=1;
}
void build(){
    int he=0,ta=1;
    q[1]=0;
    while (he!=ta){
        int x=q[++he];
        cnt[x]+=cnt[fail[x]];
        FOR(i,0,25){
            int y=son[x][i];
            if (!y) continue;
            if (x){
                int tmp=fail[x];
                while (tmp && !son[tmp][i]) tmp=fail[tmp];
                fail[y]=son[tmp][i];
            }
            q[++ta]=y;
        }
    }
}
void fnd(){
    x=0;
    FOR(i,0,m-1){
        while (x && !son[x][s[i]-'a']) x=fail[x];
        if (son[x][s[i]-'a']) x=son[x][s[i]-'a'];
        ans+=cnt[x];
    }
}
int main(){
    scanf("%d",&n);
    FOR(i,1,n){
        scanf("%s",s);
        m=strlen(s);
        ins();
    }
    build();
    scanf("%s",s);
    m=strlen(s);
    fnd();
    cout<<ans<<endl;
    return 0;
}

基础练习题

http://codeforces.com/contest/86/submission/33919169

http://codeforces.com/contest/163/submission/33955397

http://codeforces.com/contest/696/submission/33960564

 

http://codeforces.com/contest/547/submission/34041438

每个串可以看成是它的所有的前缀,fail树上能走到k的是合法的,转化为静态二维数点。

CF710F强在AC自动机(留坑


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter