Note: This article is available in Chinese only. 本文暂无英文版本。
View original
题意：给一个字符串，求这个字符串的每个前缀（包括本身）的能否由k个子串组成（K>1）
思路：和poj 2406 比较类似。。
结论：字符编号从0开始，如果又i%(i-next[i])==0，则i前面的 串为一个轮回串，其中轮回子串出现i/(i-next[i])次。
证明类似之前最小覆盖中的，不断的等价交换，两两相等…（这个证明在字符串这里总是遇到2333）
然而其实我。。。做的时候。。并没有想到去证明。。。而是打印出了nxt数组然后找规律求得2333.
之前一直觉得找规律不是什么拿的上台面的做法。。。但是今年打了几场多校。。尤其是电子科大的那场。。。我发现。。。其实有的题目的正解就是找规律，猜结论。。。
代码实现
1/* ***********************************************
2Author :111qqz
3Created Time :2016年08月11日 星期四 03时20分44秒
4File Name :code/hdu/1358.cpp
5************************************************ */
6#include <cstdio>
7#include <cstring>
8#include <iostream>
9#include <algorithm>
10#include <vector>
11#include <queue>
12#include <stack>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <deque>
19#include <ctime>
20#define fst first
21#define sec second
22#define lson l,m,rt<<1
23#define rson m+1,r,rt<<1|1
24#define ms(a,x) memset(a,x,sizeof(a))
25typedef long long LL;
26#define pi pair < int ,int >
27#define MP make_pair
28using namespace std;
29const double eps = 1E-8;
30const int dx4[4]={1,0,0,-1};
31const int dy4[4]={0,-1,1,0};
32const int inf = 0x3f3f3f3f;
33const int N=1E6+7;
34int nxt[N];
35char a[N];
36int n ;
37void getnxt( char *s)
38{
39 int i = 0 ;
40 int j = -1;
41 nxt[0] = -1;
42 int n = strlen(s);
43 while (i<n)
44 if (j==-1||s[i]==a[j]) nxt[++i]=++j;
45 else j = nxt[j];
46}
47int main()
48{
49 #ifndef ONLINE_JUDGE
50 freopen("code/in.txt","r",stdin);
51 #endif
52 int cas = 0 ;
53 while (~scanf("%d",&n))
54 {
55 if (n==0) break;
56 printf("Test case #%d\n",++cas);
57 scanf("%s",a);
58 getnxt(a);
59// for ( int i = 0 ; i <= n ; i++ ) printf("nxt[%d]:%d\n",i,nxt[i]);
60 for ( int i = 1 ; i <= n ; i++)
61 {
62 if (nxt[i]==0) continue; //因为题目要求k>1
63 int tmp = i-nxt[i];
64 if (i%tmp==0)
65 printf("%d %d\n",i,i/tmp);
66 }
67 printf("\n");
68 }
69 #ifndef ONLINE_JUDGE
70 fclose(stdin);
71 #endif
72 return 0;
73}