題意：
? ? ? 給你一個字符串，長度小于1百萬，問你他最多可以拆成集合相同字符串，例如abcabcabc 可以拆成3個abc,所以輸出3.


思路：
? ? ? 這個是比較常規的next應用，首先假設當前字符串長度n;那么
n - next[n]前綴為最短子串長度，如果n - next[n] != 0 && n / (n - next[n]) == 0,說明最后一個字符串是長度（n - next[n]）子串的最后一位，那么直接輸出n/(n-next[n])就行了，否則不是最后一位，輸出1 ，例如abcab 最后n - next[n]應該等于3，說明最短子串是3，而5 % 3 == 2，說明最后一個是子串中的第二個，不能做到完全循環，所以要輸出1

#include<stdio.h> #include<string.h>int next[1000005]; char str[1000005];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;else k = next[k];} }int main () {int n;while(~scanf("%s" ,str) && str[0] != '.'){n = strlen(str);get_next(n);//printf("%d\n" ,n - next[n]);if(n % (n - next[n]) == 0)printf("%d\n" ,n / (n - next[n]));else printf("1\n");}return 0; }

總結

以上是生活随笔為你收集整理的POJ2406 KMP前缀周期的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。