codeforces 235C - Cyclical Quest

CF235C.cpp

#include <cstdio>
#include <algorithm>
#include <cstring>
const int N = 1000000 * 2 + 9;
int f[N],vis[N],Time,b[N],t[N],n;
char s[N];
int l[N],fa[N],ch[N][26],last,len,cnt;
void add(int c)
{
	int p = last,np = ++cnt; last = np;
	l[np] = ++len; f[np] = 1;
	for (; p && !ch[p][c]; p = fa[p]) ch[p][c] = np;
	if (!p) fa[np] = 1;
	else {
		int q = ch[p][c];
		if (l[p] + 1 == l[q]) fa[np] = q;
		else {
			int nq = ++cnt;
			fa[nq] = fa[q]; memcpy(ch[nq],ch[q],sizeof ch[q]);
			l[nq] = l[p] + 1;
			fa[q] = fa[np] = nq;
			for (; ch[p][c] == q; p = fa[p]) ch[p][c] = nq;
		}
	}
}
void dp()
{
	for (int i = 2; i <= cnt; ++i) ++b[l[i]];
	for (int i = 1; i <= len; ++i) b[i] += b[i - 1];
	for (int i = 2; i <= cnt; ++i) t[b[l[i]]--] = i;
	for (int i = cnt - 1; i; --i) f[fa[t[i]]] += f[t[i]];
}
int calcans()
{
	int ans = 0;
	++Time;
	for (int i = 0,p = 1,ml = 0; i < len; ++i) {
		while (p && !ch[p][s[i] - 'a']) p = fa[p];
		if (!p) p = 1,ml = 0;
		else {
			ml = std::min(ml,l[p]) + 1;
			p = ch[p][s[i] - 'a'];
		}
		while (l[fa[p]] >= len / 2) ml = l[p = fa[p]];
		if (ml >= len / 2 && vis[p] != Time) {
			ans += f[p];
			vis[p] = Time;
		}
	}
	return ans;
}
int main()
{
	#ifndef ONLINE_JUDGE
	freopen("235C.in","r",stdin);
	freopen("235C.out","w",stdout);
	#endif
	scanf("%s",s);
	cnt = last = 1; 
	for (int i = 0,m = strlen(s); i < m; ++i) add(s[i] - 'a');
	dp();
	scanf("%d\n",&n);
	while (n--) {
		scanf("%s",s);
		len = strlen(s);
		for (int i = 0; i < len; ++i) s[i + len] = s[i];
		len *= 2;
		printf("%d\n",calcans());
	}
}