【AtCoder Regular Contest 077 F】SS
KMP，找规律，border。
题目大意：
定义字符串 $S$ 是偶串，当且仅当它是两个完全相等的字符串拼接而成。如 abaaba 和 aaaa 是偶串，qaqaq 不是偶串。
定义 $f(S)$ 为一个字符串，表示在 $S$ 后面添加最少的字符（至少 $1$ 个）使得它是偶串。可以证明当 $S$ 非空时，$f(S)$ 唯一存在。
现在给定偶串 $S$，求 $f(f(f(\cdots f(S))))$（迭代了足够多次）的第 $l\sim r$ 位中，每个字符的出现次数。
题解：
我们考虑用 SS 表示原来的 $S$（即考虑偶串的两个部分）。
通过打表找规律等方式可以发现一些性质：当 S 不由某个字符串循环两次以上组成时，令 T 为 S 去掉它的 border 后的前缀（比如：若 S 为 aba，则 T 为 ab）。那么经过一次迭代，S 就变成了 ST。
这个其实也不难理解，相当于 SS 去掉 S 的 border 之后翻倍，这个 border 就变成了第二个循环的开头。
那么我们继续迭代会怎么样呢？由于 T 是 S 的前缀，所以 T 就变成了新一轮的 border（不可能更长），那么字符串就变成 STS。接下来就是 STSST，STSSTSTS，$\ldots$。
可以发现这是斐波那契数列的增长方式，所以在 $O(\log n)$ 次迭代之后就会到达上限。故我们可以暴力求出每次迭代完后每个字符的出现次数。
由于前面和后面是一样的，所以直接从长的到短的贪心地匹配即可。
至于 S 由某个字符串循环两次以上组成的情况，最后显然是那个循环节不停地加。这种情况就非常简单了。
用 $[1,R]$ 的答案减去 $[1,L-1]$ 的答案即可。
Code：
#include<cstdio>
#include<cstring>
const int N=255555;
typedef long long LL;
struct data{
LL len,a[26];
inline void operator+=(const data&rhs){
len+=rhs.len;
for(int i=0;i<26;++i)a[i]+=rhs.a[i];
}
inline data operator-(const data&rhs)const{
data c;
c.len=0;
for(int i=0;i<26;++i)c.a[i]=a[i]-rhs.a[i];
return c;
}
}d[500],ans;
char s[N];
int fail[N],n;
LL L,R;
void getfail(){
for(int i=2,j=0;i<=n;++i){
while(j&&s[j+1]!=s[i])j=fail[j];
if(s[j+1]==s[i])++j;
fail[i]=j;
}
}
data solve(LL R){
data ret;
for(int i=ret.len=0;i<26;++i)ret.a[i]=0;
if(n%(n-fail[n])==0){
LL k=R/n;
for(int i=1;i<=n;++i)ret.a[s[i]-'a']+=k;
for(int i=1;i<=R%n;++i)++ret.a[s[i]-'a'];
}else{
memset(d,0,sizeof d);
int tot=2;
d[2].len=n;
for(int i=1;i<=n;++i)++d[2].a[s[i]-'a'];
d[1].len=n-fail[n];
for(int i=1;i<=n-fail[n];++i)++d[1].a[s[i]-'a'];
while(d[tot].len<=R){
++tot;
d[tot]=d[tot-1],d[tot]+=d[tot-2];
}
for(int i=tot;i;--i)
if(R>=d[i].len)R-=d[i].len,ret+=d[i];
for(int i=1;i<=R;++i)++ret.a[s[i]-'a'];
}
return ret;
}
int main(){
scanf("%s%lld%lld",s+1,&L,&R);
n=strlen(s+1)>>1;
getfail();
ans=solve(R);
ans=ans-solve(L-1);
for(int i=0;i<26;++i)
printf("%lld ",ans.a[i]);
return 0;
}