題目大意:
白書例題
給出一個長度不超過1000000的字元串S, 對于該字元串的所有字首求其周期, 如果周期K >= 2輸出起始位置是第幾個字元和其周期K
每一個Test case之後都要有一個空行
大緻思路:
就是利用KMP的next數組的性質對于長度為n的字元串如果n % (n - next[n]) == 0則是周期串, 周期的部分長度為n - next[n], 周期數為 n / (n - next[n])
從頭到尾掃描一次next數組即可, 時間複雜度O(|S|)
代碼如下:
Result : Accepted Memory : ? KB Time : 49 ms
/*
* Author: Gatevin
* Created Time: 2015/2/11 15:47:42
* File Name: Mononobe_Mitsuki.cpp
*/
#include<iostream>
#include<sstream>
#include<fstream>
#include<vector>
#include<list>
#include<deque>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cctype>
#include<cmath>
#include<ctime>
#include<iomanip>
using namespace std;
const double eps(1e-8);
typedef long long lint;
char in[1000010];
int next[1000010];
int n;
void KMP()
{
memset(next, 0, sizeof(next));
for(int i = 1; i < n; i++)//動态規劃求next數組
{
int j = i;
while(j != 0)
{
j = next[j];
if(in[j] == in[i])
{
next[i + 1] = j + 1;
break;
}
}
}
for(int i = 1; i <= n; i++)//依次判斷周期
if(i % (i - next[i]) == 0 && i /(i - next[i]) >= 2)
printf("%d %d\n", i, i / (i - next[i]));
printf("\n");
}
int main()
{
int cas = 1;
while(scanf("%d", &n), n)
{
scanf("%s", in);
printf("Test case #%d\n", cas++);
KMP();
}
return 0;
}