題意：
? ? ? 給你一個(gè)字符串，讓你找到一些字符串，這個(gè)字符串是從第一個(gè)字母開始的，并且他可以分成1個(gè)一上循環(huán)子結(jié)構(gòu)夠成的，比如 abcabcabc ?那么當(dāng)前的這個(gè)串就是三個(gè)abc構(gòu)成的，他的AK值就是3，對于輸出的答案中就會包含當(dāng)前這個(gè)狀態(tài)，表示為9 3。


思路：
? ? ? 就像最小路徑覆蓋是二分匹配的一個(gè)景點(diǎn)應(yīng)用一樣，這種循環(huán)節(jié)的也是KMP的一個(gè)應(yīng)用，結(jié)論是?
當(dāng) i % (i - next) == 0時(shí)，如果 i/(i - next[i]) > 1就輸出 i ,i/(i-next[i]);

我對next[i]的理解是，next[i]保存的是當(dāng)i匹配失敗的時(shí)候，盡可能的可以不往前跑的那個(gè)坐標(biāo)，也可以說找兩個(gè)相同的字符串字符串，一個(gè)是以失配點(diǎn)前一個(gè)點(diǎn)為終點(diǎn)，另一個(gè)是以第一個(gè)點(diǎn)為起點(diǎn)，這兩個(gè)串可以交叉但不可以完全相同，最長的這個(gè)串的長度的下一個(gè)就是匹配失敗后可以直接匹配的點(diǎn)，也就是 比如1231231234 假如匹配到4的時(shí)候失配了，那么就直接退到123123的后面而不是退到起始點(diǎn)，這樣就節(jié)省了沒必要的比較。

#include<stdio.h>#define N 1000000 + 100 char str[N]; int next[N];void get_next(int m) {int j ,k;j = 0 ,k = -1;next[0] = -1;while(j < m){if(k == -1 || str[j] == str[k])next[++j] = ++k;elsek = next[k];}return ; }int main () {int n ,i ,cas = 1;while(~scanf("%d" ,&n) && n){scanf("%s" ,str);get_next(n);printf("Test case #%d\n" ,cas ++);for(i = 2 ;i <= n ;i ++){if(i % (i - next[i]))continue;int tmp = i / (i - next[i]);if(tmp > 1)printf("%d %d\n" ,i ,tmp);}printf("\n");}return 0; }

《新程序員》：云原生和全面數(shù)字化實(shí)踐50位技術(shù)專家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結(jié)

以上是生活随笔為你收集整理的hdu1358 最小循环节，最大循环次数 KMP的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。