2016-10-09

HDU 5853 Jong Hyok and String【后缀自动机】

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=5853

题意：

给定$n$个字符串，$m$个询问，对于每个询问中的字符串，求$n$个串中有多少个和其$right$集相同的子串。
数据范围：$1 \le n \le 100000, 1 \le m \le 500000$

分析：

对于多个字符串建立后缀自动机，对于询问串放在后缀自动机上跑一遍。
以字符串$Q$最后一个字符为最后一个字符的后缀长度在$(st[st[now].link].len, st[now].len]$之间，就是说长度在这个范围内的所有子串都满足题意，个数也可以计算出来了。

代码：

/*************************************************************************
    > File Name: 5853.cpp
    > Author: jiangyuzhu
    > Mail: 834138558@qq.com 
    > Created Time: 2016/10/9 16:46:37
 ************************************************************************/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<algorithm>
using namespace std;
struct state {
    int len, link;
    int nex[26];
};
const int maxn = 123456, maxs = 100000;
state st[maxs * 2];
int sz, last;  
void sa_init() 
{
    sz = last = 0;
    st[0].len = 0;
	memset(st[0].nex, -1, sizeof(st[0].nex));
	st[0].link = -1;
    ++sz;
}  
//root is 0
void sa_extend (int c) 
{
    int cur = sz++;
	memset(st[cur].nex, -1, sizeof(st[cur].nex));
    st[cur].len = st[last].len + 1;
    int p;
    for (p = last; p != -1 && st[p].nex[c] == -1; p = st[p].link)
        st[p].nex[c] = cur;
    if (p == -1)
        st[cur].link = 0;
    else {
        int q = st[p].nex[c];
        if (st[p].len + 1 == st[q].len)
            st[cur].link = q;
        else {
            int clone = sz++;
            st[clone].len = st[p].len + 1;
            memcpy(st[clone].nex, st[q].nex, sizeof(st[q].nex));
            st[clone].link = st[q].link;
            for (; p!=-1 && st[p].nex[c] == q; p = st[p].link)
                st[p].nex[c] = clone;
            st[q].link = st[cur].link = clone;
        }
    }
    last = cur;
}
void build(char* s)
{
	last = 0;
	for(int i = 0; s[i]; ++i){
		sa_extend(s[i] - 'a');
	}
}
char s[maxn];
int main (void)
{
	int T;scanf("%d", &T);
	for(int tt = 1; tt <= T; ++tt){
		sa_init();
		int n, m;scanf("%d%d", &n, &m);
		for(int i = 0; i < n; ++i){
			scanf("%s", s);
			build(s);
		}
		printf("Case #%d:\n", tt);
		for(int i = 0; i < m; ++i){
			scanf("%s", s);
			int now = 0;
			bool flag = false;
			for(int j = 0; s[j]; ++j){
				now = st[now].nex[s[j] - 'a'];
				if(now == -1){
					flag = true;
					puts("0");
					break;
				}
			}
			if(!flag) printf("%d\n", st[now].len - st[st[now].link].len);
		}
	}
	return 0;
}