135、前缀数量大比拼.docx

解题思路

本题主要考察了KMP算法和在?next?数组上递推的能力。

由题意，解题的关键是，计算一个字符串包含另一个字符串所有前缀的数量。

假设我们要计算字符串?s?包含字符串?t?所有前缀的数量。我们先来看一个普通的问题，计算字符串?s?包含字符串?t?的数量。KMP常见的做法是，求出?t?的?next?数组，然后在?s?上跑KMP算法，就可以求出来?s?包含?t?所有次数了。下面是代码模板：

for(inti=1,j=0;i=n;i++){

while(jt[j+1]!=s[i])j=ne[j];

if(t[j+1]==s[i])j++;

if(j==n){//匹配成功

j=ne[j];

cnt++;

}

}

我们可以发现，当?j=n?时，s[i?j+1,i]=t，也就是完成了匹配。那么，j=1j=1?时，满足s[i?j+1,i]=t[1,1]，j=2j=2?时，满足s[i?j+1,i]=t[1,2]。举一反三，其实就是在跑KMP算法的过程中，一定有?s[i-j+1,i]=t[1,j](j0)s[i?j+1,i]=t[1,j](j0)。这个时候，我们用一个长度为?n?的cnt?数组来记录在KMP匹配时，不同?jj?出现的次数。我们可以得到下列代码：

vectorLLcnt(n+1);

for(inti=1,j=0;i=n;i++){

while(jt[j+1]!=s[i])j=ne[j];

if(t[j+1]==s[i])j++;

if(j)cnt[j]++;

if(j==n){

j=ne[j];

}

}

最后我们对cnt?求和，就可以得到?t?前缀的在?s?中通过KMP匹配到的次数。但是将这个次数累加起来并不会得到答案，原因是什么呢？

假设求字符串?aaaaa?包含字符串aaaaa?的数量，通过通过上面的代码跑出来?cnt?数组是这样的：{1,1,1,1,11,1,1,1,1}，求和起来为?5，与答案?15?不符。是因为在用KMP匹配的时候，优先匹配的是更长的前缀。意思是如果一个更长的前缀包含若干个相对短的前缀，cnt?只会记录最长前缀的次数，较短的前缀就不会记录了，因此会答案错误。要解决这个问题也很简单，就是计算每个前缀包含其他前缀的数量，那不就是?next?数组的运用吗？对于每个长度为?ii?的前缀，一定包含了一个长度为?next[i]?的后缀，而这个后缀是长度为?next[i]?的前缀，相当于每个长度为?i?的前缀包含了一个长度为?next[i]?的前缀。那么只需要从大到小枚举不同长度的前缀数量递推即可，代码片段如下：

for(inti=n;i=1;i--){

cnt[ne[i]]+=cnt[i];

}

之后再将?cnt?数组求和，就是字符串?s?包含字符串?t?所有前缀的数量了。

解法二：这个解法和上述解法相似，但只需要跑一次KMP就能得到?cnt?数组。做法是构造一个新的字符串?p=tp=t?++?#?++?ss，其中#是分隔符，不能在?s?和?t?中出现。然后求出新字符串?p?的?next?数组，不妨设?tt?长度为?mm，pp?长度为?n，那么统计一遍?next[m+1,n]?的所有值，就可以得到?cnt?数组了，后面的处理和解法一相同。

AC_Code

C++（解法一）

#includebits/stdc++.h

usingnamespacestd;

usingLL=longlong;

LLcal(conststrings,conststringt){

intn=s.size()-1;

vectorintne(n+1);

for(inti=2,j=0;i=n;i++){

while(jt[j+1]!=t[i]){

j=ne[j];

}

if(t[j+1]==t[i]){

j++;

}

ne[i]=j;

}

vectorLLcnt(n+1);

for(inti=1,j=0;i=n;i++){