題意：找出所有前綴長度，使得這個長度的前綴==後綴
Sample Input
ababcababababcabab
aaaaa
Sample Output
2 4 9 18
1 2 3 4 5
看瞭HDU 1686 Oulipo
相信next值的意義就很清晰瞭
下面給出描述: (i>1)[下標從0開始]
next[i]的意義就是：前面長度為i的字串的【前綴和後綴的最大匹配長度】
那麼這題怎麼利用這個性質呢？
詳細分析一下：【就用上面的第一個例子說明吧】
求出next值：[非修正]
下標： 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
串： a b a b c a b a b a b a b c a b a b
next值： -1 0 0 1 2 0 1 2 3 4 3 4 3 4 5 6 7 8 9
len2 = 18 next[len2] = 9
說明對於前面長度為18的字符串，【長度為9的前綴】和【長度為9的後綴】是匹配的, 即上圖的藍色跟紅色匹配
也就是整個串的最大前後綴匹配長度就是9瞭
所以接下來根本不需要考慮長度大於9的情況啦
好瞭！既然現在隻需考慮長度小於9的前後綴匹配情況，那麼
[問題就轉化成藍色串的前綴跟紅色串的後綴的匹配問題瞭！！！
又因為藍串==紅串
所以問題又轉化成
找藍串自己的前綴跟自己的後綴的最大匹配瞭！！！
那麼我們現在就要找next[9]的值瞭【next[9]的含義：藍串的最大前後綴匹配】
回憶第一步：我們找的是next[len2]=9【len2=18】
怎麼使得第二部目標變成9【求next[9]】呢？
其實next[len2]=9同時可以表示為：最大匹配前後綴的【前綴長度】
那麼next[9]的意義就是：
【主串】的最大匹配前後綴的【前綴】的【最大匹配前後綴】瞭！！
也就是上面藍串的前後綴最大匹配長度瞭！！
那麼算法描述就是：
第一步：求next[len2], 即next[18] = 9;
第二步：把9代進來，即求next[9] = 4;
第三步：把4代進來，即求next[4] = 2；
第四步：next[2] = 0; 也就是下標2之前的串已經沒有前後綴可以匹配瞭
所以答案就是： 2 4 9 18 【PS: 從小到大輸出，18是串長，必然符合題意】
局部實現代碼：
C++代碼
j = next[len2];
while (j > 0)
ans[k++] = j, j = next[j]; //ans儲存答案
C++代碼
#include <iostream>
#include <fstream>
#include <algorithm>
#include <string>
#include <set>
//#include <map>
#include <queue>
#include <utility>
#include <stack>
#include <list>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <ctype.h>
using namespace std;
#define L2 400005
int next[L2], len2, ans[L2];
char p[L2];
bool hash[L2];
void get_next() //原始next函數
{
int k = -1, j = 0;
next[0] = -1;
while (j < len2)
{
if (k == -1 || p[j] == p[k])
{
j++, k++;
next[j] = k;
}
else k = next[k];
}
/*for (j = 0; j <= len2; j++)
cout << next[j] << ;
cout << endl;*/
}
int main()
{
int k, i, j;
while (scanf (“%s”, p) != EOF)
{
k = 0;
memset (hash, false, sizeof(hash));
len2 = strlen (p);
get_next();
j = next[len2];
while (j > 0)
ans[k++] = j, j = next[j];
for (i = k – 1; i >= 0; i–) //倒過來輸出，就是從小到大瞭
printf (“%d “, ans[i]);
printf (“%d
“, len2);
}
return 0;
}
