POJ2752 Seek the Name, Seek the Fame
发布时间：2020-12-13 21:10:30 所属栏目：PHP教程 来源：网络整理
导读：问题链接：POJ2752 Seek the Name,Seek the Fame。 读懂题后知道，这个题要算的是，给定1个字符串s，有 哪些长度的s的前缀，同时也是s的后缀。 首先明确1下前缀和后缀的概念。字符串s的前缀是指，从s的开始字符到s的任意字符为止的子串。 字符串s的后缀是指
|
问题链接：POJ2752 Seek the Name,Seek the Fame。 读懂题后知道，这个题要算的是，给定1个字符串s，有哪些长度的s的前缀，同时也是s的后缀。 首先明确1下前缀和后缀的概念。字符串s的前缀是指，从s的开始字符到s的任意字符为止的子串。字符串s的后缀是指，从s的任意字符到s的最后字符为止的子串。s是既是本身的前缀也是本身的后缀。 这个问题利用KMP算法的next[]数组来解。首先对输入的字符串s，计算其next[]数组。然后，根据next[]数组的值进行进1步的计算。 还需要知道的是next[]数组的定义。对字符串s的第i个字符s[i]，next[i]定义为字符s[i]前面最多有多少个连续的字符和字符串s从初始位置开始的字符匹配。 从后到前匹配前缀和后缀。如果前缀与后缀匹配，则下1个前缀与后缀匹配的字符串只能在前缀中。 AC程序以下：
/* POJ2752 Seek the Name,Seek the Fame */
#include <stdio.h>
#include <string.h>
char s[400000+1];
int next[400000+1];
int result[400000+1];
void setnext(char s[],int next[],int len)
{
next[0] = ⑴;
int i = 0,j = ⑴;
while (i < len)
{
if (j == ⑴ || s[i] == s[j]) {
++i;
++j;
next[i] = j;
} else
j = next[j];
}
}
int main(void)
{
int count,t,i;
while(scanf("%s",s) != EOF) {
int len = strlen(s);
// 计算next[]数组值
setnext(s,next,len);
// 计算结果：从字符串的尾部开始，下1个只能在与后缀相同的前缀字符串中
count = 0;
t = next[len - 1];
while(t != ⑴) {
if(s[t] == s[len - 1])
result[count++] = t + 1;
t = next[t];
}
// 输出结果
for(i=count⑴; i>=0; i--)
printf("%d ",result[i]);
printf("%dn",len);
}
return 0;
} （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |