海亮01/08字符串

题单链接

SAM学习笔记

T1

CF235C

题意

给定一个主串\(S\)和\(n\)个询问串，求每个询问串的所有循环同构在主串中出现的次数总和。

题解

如果不问循环同构，只问正常询问串的出现次数，会吗？

直接上板子即可对叭？

那么对于循环同构，我们可以直接加长一倍（加到 \(2n-1\)，如果是 \(2n\) 就有一个重复了），那么新串所有长度为 \(n\) 的子串就可以代表所有循环同构。

然后对这样一个新串进行询问，每次添加一个字符找到最长的有这个字符转移的状态，同时更新当前已查找的子串长度。

然后如果现在已查找的子串长度超过 \(n\) 怎么办？直接暴力跳 \(link\) 树直到当前节点的长度区间包含 \(n\)。然后统计次数。

同时为了解决重复计数的问题，查询之后给这个状态打个标记，下次不统计即可，然后别忘了一个询问做完了清空标记。

Accept=Happy New Year! 好评

代码

#include<bits/stdc++.h>
using namespace std;
inline int read(){
	int x = 0, f = 1;char ch = getchar();
	while(ch < '0' || ch > '9'){if(ch == '-') f = -1;ch = getchar();}
	while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + (ch ^ 48);ch = getchar();}
	return x * f;
}
const int maxn = 1e6 + 10;
char ch[maxn];
bool book[maxn * 2];
struct SAM{
	struct node{
		int link, len, siz;
		unordered_map<char,int> nxt;
	}d[maxn * 2];
	int a[maxn * 2], cf[maxn], tot, last;
	void build(){tot = last = 0;d[0].link = -1;}
	void insert(char ch){
		int cur = ++tot;d[cur].siz = 1;
		d[cur].len = d[last].len + 1;
		int p = last;
		while(p != -1 && !d[p].nxt[ch]){d[p].nxt[ch] = cur;p = d[p].link;}
		if(p == -1){d[cur].link = 0;}
		else{
			int q = d[p].nxt[ch];
			if(d[p].len + 1 == d[q].len){d[cur].link = q;}
			else{
				int clone = ++tot;
				d[clone].link = d[q].link;
				d[clone].nxt = d[q].nxt;
				d[clone].len = d[p].len + 1;
				while(p != -1 && d[p].nxt[ch] == q){d[p].nxt[ch] = clone;p = d[p].link;}
				d[q].link = d[cur].link = clone;
			}
		}
		last = cur;
	}
	void build(char *s){
		build();
		int len = strlen(s + 1);
		for(int i = 1;i <= len;i++)insert(s[i]);
		for(int i = 0;i <= tot;i++)cf[d[i].len]++;cf[0] = 0;
		for(int i = 1;i <= len;i++)cf[i] += cf[i - 1];
		for(int i = 0;i <= tot;i++)a[cf[d[i].len]--] = i;
		for(int i = tot;i;i--){int p = a[i];d[d[p].link].siz += d[p].siz;}
	}
	int query(char *s){
		int ans = 0;
		int p = 0, len = strlen(s + 1), dep = 0;
		vector<int> vec;vec.clear();
		for(int i = 1;i < len * 2;i++){
			char ch = s[(i - 1) % len + 1];
			while(p != -1 && !d[p].nxt[ch]){p = d[p].link;dep = d[p].len;}
			if(p != -1){
				p = d[p].nxt[ch];dep++;
				while(dep > len){dep--;if(dep <= d[d[p].link].len)p = d[p].link;}
				if(dep >= len && !book[p]){ans += d[p].siz;book[p] = 1;vec.push_back(p);}
			}
			else p = 0;
		}
		for(int u : vec)book[u] = false;
		return ans;
	}
}sam;
signed main(){
	scanf("%s",ch + 1);sam.build(ch);
	for(int T = read();T;T--){
		scanf("%s",ch + 1);
		printf("%d\n",sam.query(ch));
	}
	return 0;
}