pku 2752 kmp運用

2022-11-24 21:32:04 字數 760 閱讀 1203

/*

題意:輸出首尾串相同的前段位置 ,例abbcaabb,符合的:abb--abb,abbcaabb--abbcaabb,所以輸出3,8

思路:kmp

此題對於剛接觸kmp的新手(比如說我),可以更深一點理解kmp思想

我們先看看兩個例子abbcaabb,輸出的是3,8

ababcababababcabab,輸出2,4,9,18

其實可以看出一個規律,例一:next[8] = 3;  next[3] = 0;

例二:next[18] = 9; next[9] = 4; next[4] = 2; next[2] = 0;

那麼是不是隻要把字串長度(l)輸出,然後遞迴輸出next[l] (l = next[l]) 直到為0即可

多組資料測試是這樣的,為什麼自己想想應該就能知道,我覺得kmp有時很靈活,自己想到的

或許會理解的更透徹,實現見**

*/

#include #include char s[400003];

int next[400003];

int a[400003];

int len;

void getnext()

next[i] = j; }}

void print()

for(int i=num-1;i>0;i--) printf("%d ",a[i]);

printf("%d\n",a[0]);

}int main()

return 0;

}

poj2752(kmp)

昨天寫完以後wa了好幾次,今天發現邊界條件的判斷有問題,就修改了一下,結果又re了幾次。然後把陣列改大了一些就ac了。看來開陣列真不能小氣呀!要把陣列開的儘量大一些。kmp最關鍵的地方就是理解目標字串匹配的過程。假設目標字串是ababde,dist i 表示當匹配到第i個字元後匹配失敗應用第幾個字元...

POJ2752 KMP next陣列含義

題意 給一個字串,求滿足既是這個字串的字首,又是這個字串的字尾,從小到大輸出長度 思路 細講next陣列含義博文 點我 首先要滿足字首的呀。kmp的next陣列乾的是子串最長字尾。所以從最後一個next一直往前跳,next存的就是最長字尾,知道為0 1 include include include...