poj 2752 Seek the Name, Seek the Fame【KMP算法分析记录】【求前后缀相同的子串的长度】

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

Seek the Name, Seek the Fame

Time Limit: 2000MS		Memory Limit: 65536K
Total Submissions: 14106		Accepted: 7018

Description

The little cat is so famous, that many couples tramp over hill and dale to Byteland, and asked the little cat to give names to their newly-born babies. They seek the name, and at the same time seek the fame. In order to escape from such boring job, the innovative little cat works out an easy but fantastic algorithm:

Step1. Connect the father's name and the mother's name, to a new string S.
Step2. Find a proper prefix-suffix string of S (which is not only the prefix, but also the suffix of S).

Example: Father='ala', Mother='la', we have S = 'ala'+'la' = 'alala'. Potential prefix-suffix strings of S are {'a', 'ala', 'alala'}. Given the string S, could you help the little cat to write a program to calculate the length of possible prefix-suffix strings of S? (He might thank you by giving your baby a name:)

Input

The input contains a number of test cases. Each test case occupies a single line that contains the string S described above.

Restrictions: Only lowercase letters may appear in the input. 1 <= Length of S <= 400000.

Output

For each test case, output a single line with integer numbers in increasing order, denoting the possible length of the new baby's name.

Sample Input

ababcababababcabab
aaaaa

Sample Output

2 4 9 18
1 2 3 4 5题意：求所有前缀和后缀相同的子串的长度
题解：首先了解什么是前缀和后缀
1、前缀：从第一位开始依次取字符串中字符所组成的子串如字符串abcd其前缀为:a,ab,abc,abcd注意abcd也算其前缀
2、后缀：从最后一位开始依次向前取字符串中的字符组成的子串如abcd其后缀为：d,cd,bcd,abcd
我们所求的失配函数f[]其失配值f[i]就是从0到i的前缀后缀相同的最大子串的长度如

求失配函数：
方法一、我们一起求一下这组数据的前后缀（即失配函数的值）f[0]=0;
（不考虑整条字符串本身）
a的前后缀都为空(1位置 f[1]=0)
ab的前缀为a,后缀为b不相等(f[2]=0)
abc的前缀为a,ab后缀为bc,b不相等(f[3]=0)
abcd的前缀为a,ab,abc后缀为bcd,cd,d没有相等的(f[4]=0)
abcda的前缀为a,ab,abc,abcd,后缀为bcda,cda,da,a有相同的前后缀a且长度为1(f[5]=1)
以此类推得到f[6]=2,f[7]=0;
方法二、

另一种方法求失配函数

规定f[0]=f[1]=0(失配函数第0位和第1为毕等0)

给一组数据来说明求的方法：
0 1 2 3 4 5 6 7
a b c d a b d
0 0
第0和第1位已经确定现在从第2位开始求，当求c时我们需要看他前一位的
字符以及前一位的字符的失配值（f[i]值），前一位是b失配值是0，我们就来看
第0位所代表的字符是否和b相同，相同则f[2]=f[1]+1,不同则f[2]=0
这里不同所以f[3]=0,此时数据变为：
0 1 2 3 4 5 6 7
a b c d a b d
0 0 0

第3位，任然比较他的前一位，为c失配值为0我们依然拿d的前一位c同第0位比较
c和a不同所以 f[3]=0;此时数据变为：

0 1 2 3 4 5 6 7
a b c d a b d
0 0 0 0

同理f[4]=0

0 1 2 3 4 5 6 7
a b c d a b d
0 0 0 0 0

第5位前一位是a失配值为0此时第五位的a等于第0位的a所以f[5]=f[4]+1=1

0 1 2 3 4 5 6 7
a b c d a b d
0 0 0 0 0 1

第6位前一位是b失配值为1此时第六位的b等于第1位的b所以f[6]=f[5]+1=2
0 1 2 3 4 5 6 7
a b c d a b d
0 0 0 0 0 1 2

同理第七位f[7]=0;

这里我们按照方法一来继续讲解

/*
* 0 1 2 3 4 5 6 7 //字符串字符对应位置
* a b c d a b d //字符串
* 0 0 0 0 0 1 2 0 //字符串的失配值
*//*
* 当i等于1时即字符串位置是0->0此时失配值为0因为无
* 前后缀相同同理当i等2时也一样，依次类推，当i等于
* 5时字符串对应位置为0->4（长度为5）此时f[5]=1因为
* 有相同的前后缀a且长度为1，当i等于6时字符串对应位置
* 0->5此时f[6]=2因为有相同前后缀ab
* 这就验证了我们上边所说的
* 注意：在这里我们的前后缀不考虑整个字符串本身，而且
* 所求前后缀的子串时我们的i表示的长度
*/

因此我们想要求前后缀相同的子串的长度只需要求对应位置失配函数f[i]的值即可

这里以题目中两组数据为例：

/*
*0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
*a b a b c a b a b a b a b c a b a b
*0 0 0 1 2 0 1 2 3 4 3 4 3 4 5 6 7 8 9
*f[18]=9 f[9]=4 f[4]=2 f[2]=0
*所以我们只需要每次让k=f[k]，然后取 f[k]的值直到
*k等于0即可得到结果
*
*0 1 2 3 4 5
*a a a a a
*0 0 1 2 3 4
*同样f[5]=4 f[4]=3 f[3]=2 f[2]=1 f[1]=0
*/

AC代码：

#include<stdio.h>
#include<string.h>
#define MAX 400100
char str[MAX];
int f[MAX];
int dp[MAX];
int len;
void getfail()
{
int i,j;
f[0]=f[1]=0;
for(i=1;i<len;i++)
{
j=f[i];
while(j&&str[i]!=str[j])
j=f[j];
f[i+1]=str[i]==str[j]?j+1:0;
}
}
void kmp()
{
int k=len;
intn=0;
while(f[k])
{
dp[n++]=f[k];
k=f[k];
}
for(int i=n-1;i>=0;i--)
printf("%d ",dp[i]);
printf("%d\n",len);
}
int main()
{
int i;
while(scanf("%s",str)!=EOF)
{
len=strlen(str);
getfail();
kmp();
}
return 0;
}