【未知来源】循环移位

题意

　　给定一个字符串 (s)，问有多少个本质不同的 (s) 的子串 (t=t_1 t_2 cdots t_mspace (mgt 0)) 使得将 (t) 循环左移一位后变成 (t'=t_2cdots t_m t_1) 也是 (s) 的一个子串。
　　对于 (10\%) 的数据 (|s|le 200)，对于 (40\%) 的数据 (|s|le 5000)，对于 (100\%) 的数据 (|s|le 3 imes 10^5)

题解

　　看到“本质不同”就知道是 SAM 模板题了……
　　本来因为题太板子不想写 ( ext{sol}) 的，后来一想回去后貌似会被封广二账号，于是存一下题和代码吧。

#include<bits/stdc++.h>
#define ll long long 
#define N 600010
using namespace std;
inline int read(){
	int x=0; bool f=1; char c=getchar();
	for(;!isdigit(c); c=getchar()) if(c=='-') f=0;
	for(; isdigit(c); c=getchar()) x=(x<<3)+(x<<1)+(c^'0');
	if(f) return x; return 0-x;
}
char s[N]; int n,sum[N][27];
ll ans;
namespace SAM{
	int len[N],pos[N],ch[N][27],fa[N],tot,lst;
	void extend(int i, int c){
		int u=lst, v=++tot; lst=v, len[v]=len[u]+1, pos[v]=i;
		for(; u && !ch[u][c]; u=fa[u]) ch[u][c]=v;
		if(!u) fa[v]=1;
		else if(len[ch[u][c]]==len[u]+1) fa[v]=ch[u][c];
		else{
			int t=++tot, o=ch[u][c]; len[t]=len[u]+1, pos[t]=pos[o];
			memcpy(ch[t],ch[o],sizeof ch[o]);
			fa[t]=fa[o], fa[o]=fa[v]=t;
			for(; u && ch[u][c]==o; u=fa[u]) ch[u][c]=t;
		}
	}
	/*
	int x[N],arr[N];
	void pSort(){
		for(int i=1; i<=tot; ++i) ++x[len[i]];
		for(int i=2; i<=n; ++i) x[i]+=x[i-1];
		for(int i=1; i<=tot; ++i) arr[x[len[i]]--]=i;
	}*/
}using namespace SAM;
int main(){
	scanf("%s",s+1), n=strlen(s+1);
	lst=++tot;
	for(int i=1; i<=n; ++i) extend(i,s[i]-'a');
	//pSort();
	for(int i=1; i<=n; ++i)
		for(int j=0; j<26; ++j)
			sum[i][j]=sum[i-1][j]+(s[i]-'a'==j);
	for(int i=2; i<=tot; ++i){
		if(ch[fa[i]][s[pos[i]-len[fa[i]]]-'a']) ++ans;
		for(int j=0; j<26; ++j)
			if(ch[i][j])
				ans+=sum[pos[i]-len[fa[i]]-1][j]-sum[pos[i]-len[i]][j];
	}
	printf("%lld
",ans);
	return 0;
}