poj 2406 Power Strings (后缀数组||kmp)

poj 2406

题意:给定一个字符串 L,已知这个字符串是由某个字符串 S 重复 R 次而得到的, 求 R 的最大值

思路:论文题.

转载论文中的题解:

做法比较简单,穷举字符串 S 的长度 k,然后判断是否满足。判断的时候, 先看字符串 L 的长度能否被 k 整除,**再看 suffix(1)和 suffix(k+1)的最长公共** **前缀是否等于 n-k**。在询问最长公共前缀的时候,suffix(1)是固定的,所以 RMQ 问 题 没 有 必 要 做 所 有 的 预 处 理 , 只 需 求 出 height 数 组 中 的 每 一 个 数 到 height[rank[1]]之间的最小值即可。整个做法的时间复杂度为 O(n)

最关键的在加黑的那句话:看 suffix(1)和 suffix(k+1)的最长公共 前缀是否等于 n-k

why???

转载一段证明:

为什么这样就行了呢?这要充分考虑到后缀的性质。当lcp(1,k+1)=n-k时,后缀k+1是后缀1(即整个字符串)的一个前缀。(因为后缀k+1的长度为n-k)那么,后缀1的前k个字符必然和后缀k+1的前k个字符对应相同。**而后缀1的第k+1..2k个字符,又相当于后缀k+1的前k个字符,所以与后缀1的前k个字符对应相同,且和后缀k的k+1..2k又对应相同**。依次类推,只要lcp(1,k+1)=n-k,那么s[1..k]就可以通过自复制n/k次得到整个字符串。找出k的最小值,就可以得到n/k的最大值了。

虽然这道题不适合用后缀数组做,倍增会tle,dc3也是卡时间才能过,但是接触到了一个想法.

要看一个字符串s能否由一个较小的长度为k的字符串t重复若干次得到,除了要整除以外,

gengxin判断suffix(1)和 suffix(k+1)的最长公共****前缀是否等于 n-k即可.

下面是用倍增写的tle了的代码,价值在于那段没有用rmq,而是o(n)更新height数组到height[rk[0]]之间的最小值要怎么写.

 1/* ***********************************************
 2Author :111qqz
 3Created Time :2016年08月02日 星期二 19时41分08秒
 4File Name :code/poj/2406.cpp
 5************************************************ */
 6#include <cstdio>
 7#include <cstring>
 8#include <iostream>
 9#include <algorithm>
10#include <vector>
11#include <queue>
12#include <set>
13#include <map>
14#include <string>
15#include <cmath>
16#include <cstdlib>
17#include <ctime>
18#define fst first
19#define sec second
20#define lson l,m,rt<<1
21#define rson m+1,r,rt<<1|1
22#define ms(a,x) memset(a,x,sizeof(a))
23typedef long long LL;
24#define pi pair < int ,int >
25#define MP make_pair
26using namespace std;
27const double eps = 1E-8;
28const int dx4[4]={1,0,0,-1};
29const int dy4[4]={0,-1,1,0};
30const int inf = 0x3f3f3f3f;
31const int N=1E6+7;
32int n,sa[N],rk[N],t[N],t2[N],cnt[N];
33int height[N];
34char s[N];
35int cmp( int *r,int a,int b,int l){return r[a]==r[b]&&r[a+l]==r[b+l];}
36void getSa( int n,int m)
37{
38    int *x=t;
39    int *y=t2;
40    ms(cnt,0);
41    for ( int i = 0 ; i < n;  i++) cnt[x[i]=s[i]]++;
42    for ( int i = 1;  i < m ; i++) cnt[i]+=cnt[i-1];
43    for ( int i = n-1 ; i >= 0 ; i--) sa[--cnt[x[i]]] = i ;
44    for ( int k = 1 ; k <= n ; k<<=1)
45    {
46	int p = 0;
47	for ( int i = n- k; i < n ; i++) y[p++] =i;
48	for ( int i = 0 ; i < n;  i++) if (sa[i]>=k) y[p++] = sa[i]-k;
49	ms(cnt,0);
50	for ( int i = 0 ; i < n ; i++) cnt[x[y[i]]]++;
51	for ( int i = 0 ; i <m ; i ++) cnt[i]+=cnt[i-1];
52	for ( int i = n-1 ; i >= 0 ; i--) sa[--cnt[x[y[i]]]] = y[i];
53	swap(x,y);
54	p = 1;
55	x[sa[0]] = 0 ;
56	for ( int i = 1; i  <n ; i++)
57	    x[sa[i]] = cmp(y,sa[i-1],sa[i],k)?p-1:p++;
58	if (p>=n) break;
59	m = p;
60    }
61}
62void getHeight( int n)
63{
64    int k = 0 ;
65    for ( int i = 0 ;i <n ; i++) rk[sa[i]] = i ;
66    height[0] = 0 ;
67    for ( int i = 0 ; i < n;  i++)
68    {
69	if (rk[i]==0) continue;
70	if (k)  k--;
71	int j = sa[rk[i]-1];
72	while (s[i+k]==s[j+k]) k++;
73	height[rk[i]] = k ;
74    }
75}
76int getSuffix( char s[])
77{
78    int up = 0 ;
79    int len = strlen(s);
80    for ( int i = 0 ; i < len; i++)
81    {
82	int val = s[i];
83	up = max(up,val);
84    }
85    s[len++] = '$' ;
86    getSa(len,up+1);
87    getHeight(len);
88    return len;
89}
1int lcp[N];
2int solve( int n)
3{
4    int st = rk[0];
5    lcp[st] = inf;
6    for ( int i = st-1 ; i ; i--)
7	lcp[i] = min(lcp[i+1],height[i+1]);
8    for ( int i = st+1 ; i <= n ; i++)
9	lcp[i] = min(lcp[i-1],height[i]);
1    for ( int k = 1 ; k <= n ; k++)
2	if (n%k==0)
3	    if (lcp[rk[k]]==n-k)
4		return n/k;
    return 1;
 1}
 2int main()
 3{
 4	#ifndef  ONLINE_JUDGE 
 5	freopen("code/in.txt","r",stdin);
 6  #endif
 7	while (~scanf("%s",s))
 8	{
 9	    if (s[0]=='.') break;
10	    int len = getSuffix(s);
11	    cout<<endl;
12	    int ans = solve(len-1);
1//	    for ( int i = 0 ; i < len; i++) cout<<"i:"<<i<<" height[i]:"<<height[i]<<" rk[i]:"<<rk[i]<<" lcp[i]"<<lcp[i]<<endl;
2	    printf("%d\n",ans);
3	}
4  #ifndef ONLINE_JUDGE  
5  fclose(stdin);
6  #endif
7    return 0;
8}

kmp的思路:

KMP中的get_next(),或者get_nextval(),对next数组的应用。next[len]是最后一个字符跳的步长,如果他有相同字符串,则该串长度是len-next[len](这点我还在想要怎么证明!)...如果整个长度len能分解成x个这种串(能整除),就得到ans了。否则不能分解。只能是由他自己组成串,长度为1。

这道题用kmp非常块...

但是其实............

其实...........

其实我不会kmp......................

搞完后缀数组去学下.

/* ***********************************************
Author :111qqz
Created Time :2016年08月02日 星期二 21时27分44秒
File Name :code/hdu/r2406.cpp
************************************************ */
 1#include <cstdio>
 2#include <cstring>
 3#include <iostream>
 4#include <algorithm>
 5#include <vector>
 6#include <queue>
 7#include <set>
 8#include <map>
 9#include <string>
10#include <cmath>
11#include <cstdlib>
12#include <ctime>
13#define fst first
14#define sec second
15#define lson l,m,rt<<1
16#define rson m+1,r,rt<<1|1
17#define ms(a,x) memset(a,x,sizeof(a))
18typedef long long LL;
19#define pi pair < int ,int >
20#define MP make_pair
 1using namespace std;
 2const double eps = 1E-8;
 3const int dx4[4]={1,0,0,-1};
 4const int dy4[4]={0,-1,1,0};
 5const int inf = 0x3f3f3f3f;
 6const int N=1E6+7;
 7int nxt[N];
 8char s[N];
 9void kmp(int n)
10{
11    int i = 0,j=-1;
12    nxt[0] = -1;
13    while (i<n)
14	if (j==-1||s[i]==s[j]) nxt[++i] = ++j;
15	else j = nxt[j];
16}
17int main()
18{
19	#ifndef  ONLINE_JUDGE 
20	freopen("code/in.txt","r",stdin);
21  #endif
1	while (~scanf("%s",s))
2	{
3	    if (s[0]=='.') break;
4	    int len = strlen(s);
5	    kmp(len);
6	    int k = len-nxt[len];
7	    printf("%d\n",len%k?1:len/k);
	}
1  #ifndef ONLINE_JUDGE  
2  fclose(stdin);
3  #endif
4    return 0;
5}