【洛谷 P3966】 [TJOI2013]单词（AC自动机，差分）

把单词连起来，中间插入间隔符，同
#include <cstdio>

#include <queue>

#include <cstring>

using namespace std;

struct Node{

    int fail, next[27], num;

}AC[200010];

int n, u, cnt;

queue <int> q;

int p[1000010], vis[1000010];

char a[2000010], b[1000010];

int f[1000010];

int lena;

struct Edge{

	int next, to;

}e[200010];

int head[200010], num;

inline void Add(int from, int to){

	e[++num].to = to; e[num].next = head[from]; head[from] = num;

}

void insert(int x){

    int len = strlen(b + 1), w;

    u = 0;

    for(int i = 1; i <= len; ++i){

        w = b[i] - 'a';

        if(!AC[u].next[w])

          AC[u].next[w] = ++cnt;

        u = AC[u].next[w];

    }

    f[x] = u;

}

void BuildFail(){

	u = 0;

    for(int i = 0; i < 26; ++i)

       if(AC[u].next[i])

         q.push(AC[u].next[i]);

    while(q.size()){

        u = q.front(); q.pop();

        for(int i = 0; i < 26; ++i)

           if(AC[u].next[i]){

           	 q.push(AC[u].next[i]);

             AC[AC[u].next[i]].fail = AC[AC[u].fail].next[i];

           }

           else

		     AC[u].next[i] = AC[AC[u].fail].next[i];

    }

}

void Match(){

    int len = lena;

    u = 0;

    for(int i = 1; i <= len; ++i){

        u = AC[u].next[a[i] - 'a'];

        ++vis[u];

    }

}

void dfs(int x){

	for(int i = head[x]; i; i = e[i].next){

		dfs(e[i].to); vis[x] += vis[e[i].to];

	}

}

int main(){

    scanf("%d", &n);

    for(int i = 1; i <= n; ++i) f[i] = i;

    for(int i = 1; i <= n; ++i){

     	scanf("%s", b + 1);

     	int len = strlen(b + 1);

    	insert(i);

    	for(int i = 1; i <= len; ++i)

    	   a[++lena] = b[i];

    	a[++lena] = 'z' + 1;

    }

    BuildFail();

    Match();

    for(int i = 1; i <= cnt; ++i)

       Add(AC[i].fail, i);

    dfs(0);

    for(int i = 1; i <= n; ++i)

       printf("%d\n", vis[f[i]]);

    return 0;

}
巴特西

【洛谷 P3966】 [TJOI2013]单词（AC自动机，差分）

最新文章

热门文章
