Tyvj1068 给定两个长度为2*10^5的字符串为A和B 求B在A中匹配后，任意匹配长度的位置个数。
KMP算法大家应该烂熟于心才好，这样碰到这样的题才能灵活运用。有时做题真的需要一点灵感。
首先，这个题如果想要求出从每个位置开始的字串的匹配长度，那么O(n^2)以内的算法应该是很难的。但是，这个题要求的并不是“每个位置的长度”，而是“具有这样长度的位置数”。因而，灵活使用KMP算法自我匹配的性质，就能够解决这个问题。
考虑下面的例子：
A串：abbabbabababbababba
B串：abbabababba
应用KMP算法，很容易得到B串的自我匹配是
元素 a b b a b a b a b b a
位置 1 2 3 4 5 6 7 8 9 10 11
长度 0 0 0 1 2 1 2 1 2 3 4
这个数组记为kmp[位置] = 匹配长度。
由此求得到A串的各个元素尾部的匹配长度是
a b b a b b a b a b a b b a b a b b a
1 2 3 4 5 3 4 5 6 7 8 9 10 11 5 6 7 3 4
统计出各个长度的出现频数
长度 0 1 2 3 4 5 6 7 8 9 10 11
频数 0 1 1 3 3 3 2 2 1 1 1 1
这个数组记作cnt[长度] = 频数。
根据KMP自我匹配数组的性质，如果以A串某个元素结尾有一个长度为11的字串可以与B串匹配的话，以该元素结尾的长度为kmp[11] = 4的字串也是可以匹配的。所以说cnt[4] += cnt[11]。也就是说，进行这样的操作
for (i = N; i >= 1; i--)
cnt[kmp[i]] += cnt[i];
for i := N downto 1 do
inc( cnt[ kmp[i] ] , cnt[i] );
之后，cnt[i]中保存的就应该是所有长度为i的匹配字串了。这时cnt数组的状态是
长度 0 1 2 3 4 5 6 7 8 9 10 11
频数 19 8 7 4 4 3 2 2 1 1 1 1
然而题中要求的是“长度恰好为i”的子串的个数，也就是这些字串的下一个字符是不能匹配的。然而，cnt数组中存储的cnt[i]，必然包含了cnt[i + 1]及以上的情况。然而这很简单，“长度恰好为i”的字串数量就是cnt[i] - cnt[i + 1]，因为cnt[i]中可以扩展的字串必然都包含于cnt[i + 1]。
时间复杂度O(M + N)。
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
using namespace std;
const int maxn=200000;
char a[maxn],b[maxn];
int la,lb,kmp[maxn],an[maxn],times[maxn];
int main()
{
freopen("t.txt","r",stdin);
ios::sync_with_stdio(false);
int i,j,k,m,n,t;
cin>>la>>lb>>m;
cin>>a>>b;
memset(kmp,0,sizeof(kmp));
for(i=1;i<lb;i++)
{
k=kmp[i-1];
while(k>0&&b[k]!=b[i])
k=kmp[k-1];
if(b[k]==b[i])
kmp[i]=k+1;
else kmp[i]=0;
}
k=0;
memset(an,0,sizeof(an));
for(i=0;i<la;i++)
{
do
{
if(a[i]==b[k])
{
k++;
break;
}
else k=kmp[k-1];
}while(k>0);
if(a[i]==b[k]&&k==0)an[i]=++k;
else an[i]=k;
}
memset(times,0,sizeof(times));
for(i=0;i<la;i++)
times[an[i]]++;
for(i=lb;i>=1;i--)
times[kmp[i-1]]+=times[i];
for(i=1;i<=m;i++)
{
cin>>j;
cout<<times[j]-times[j+1]<<endl;
}
return 0;
}