POJ2752 Seek the Name, Seek the Fame
來源：程序員人生 發布時間：2016-07-07 08:46:49 閱讀次數：2449次
問題鏈接：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("%d\n", len);
}
return 0;
}
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
