poj 2406 Power Strings (kmp 中 next 数组的应用||后缀数组)

Power Strings

Time Limit: 3000MS		Memory Limit: 65536K
Total Submissions: 27003		Accepted: 11311

Description

Given two strings a and b we define a*b to be their concatenation. For example, if a = "abc" and b = "def" then a*b = "abcdef". If we think of concatenation as multiplication, exponentiation by a non-negative integer is defined in the normal way: a^0 = "" (the empty string) and a^(n+1) = a*(a^n).

Input

Each test case is a line of input representing s, a string of printable characters. The length of s will be at least 1 and will not exceed 1 million characters. A line containing a period follows the last test case.

Output

For each s you should print the largest n such that s = a^n for some string a.

Sample Input

abcd
aaaa
ababab
.

Sample Output

1
4
3

思路：
理解next数组，利用next数组进行巧妙求解

 1 #include<iostream>
 2 #include<string.h>
 3 #include<stdio.h>
 4 using namespace std;
 5 #define MAX 1000000
 6 
 7 void get_next(char *str,int *next)
 8 {
 9     int i=0,j=-1;
10     int tlen=strlen(str);
11     next[0]=-1;
12     while(i<tlen)
13     {
14         if(j==-1||str[i]==str[j])
15         {
16             i++;
17             j++;
18             if(str[i]!=str[j])
19                 next[i]=j;
20             else
21                 next[i]=next[j];
22         }
23         else
24             j=next[j];
25     }
26 }
27 char str[MAX+10];
28 int next[MAX+10];
29 int main()
30 {
31     int t=1;
32     while(~scanf("%s",str))
33     {
34         if(str[0]=='.')  break;
35         get_next(str,next);
36         int len = strlen(str);
37     //    for(int i=0;i<=len;i++)  cout<<next[i]<<" "; cout<<endl;
38         if(len%(len-next[len])==0)  //next[len]为匹配到len时失配所要跳到的上一个匹配点，len-next[len]即为一个循环节
39             printf("%d
",len/(len-next[len]));
40         else
41             printf("1
");
42     }
43     return 0;
44 }

（后缀数组）思路：

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

　　算法分析：

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

以下是我超时代码：（尼玛滴不科学呀！！！）

TLE代码：跪求大神赐教！！！

  1 #include <iostream>
  2 #include <stdio.h>
  3 #include<string.h>
  4 
  5 using namespace std;
  6 
  7 #define maxn 1100000
  8 
  9 #define cls(x) memset(x, 0, sizeof(x))
 10 
 11 int wa[maxn],wb[maxn],wv[maxn],wss[maxn];
 12 
 13 int cmp(int *r,int a,int b,int l){return r[a]==r[b]&&r[a+l]==r[b+l];}
 14 
 15 //倍增算法
 16 void da(char *r,int *sa,int n,int m)
 17 {
 18      cls(wa);
 19      cls(wb);
 20      cls(wv);
 21      int i,j,p,*x=wa,*y=wb,*t;
 22 
 23      //基数排序
 24      for(i=0;i<m;i++) wss[i]=0;
 25      for(i=0;i<n;i++) wss[x[i]=r[i]]++;
 26      for(i=1;i<m;i++) wss[i]+=wss[i-1];
 27      for(i=n-1;i>=0;i--) sa[--wss[x[i]]]=i;
 28 
 29      //　在第一次排序以后，rank数组中的最大值小于p，所以让m=p。整个倍增算法基本写好，代码大约25行。
 30      for(j=1,p=1;p<n;j*=2,m=p)
 31      {
 32        //接下来进行若干次基数排序，在实现的时候，这里有一个小优化。基数排序要分两次，第一次是对第二关键字排序，第二次是对第一关键字排序。对第二关键字排序的结果实际上可以利用上一次求得的sa直接算出，没有必要再算一次
 33        for(p=0,i=n-j;i<n;i++) y[p++]=i;
 34        for(i=0;i<n;i++) if(sa[i]>=j) y[p++]=sa[i]-j;
 35 
 36        //其中变量j是当前字符串的长度，数组y保存的是对第二关键字排序的结果。然后要对第一关键字进行排序，
 37        for(i=0;i<n;i++) wv[i]=x[y[i]];
 38        for(i=0;i<m;i++) wss[i]=0;
 39        for(i=0;i<n;i++) wss[wv[i]]++;
 40        for(i=1;i<m;i++) wss[i]+=wss[i-1];
 41        for(i=n-1;i>=0;i--) sa[--wss[wv[i]]]=y[i];
 42 
 43        //这样便求出了新的sa值。在求出sa后，下一步是计算rank值。
 44        for(t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1;i<n;i++)
 45        x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;
 46      }
 47 }
 48 
 49 int rank[maxn],height[maxn];
 50 
 51 //得到height数组：排名相邻的两个后缀的最长公共前缀
 52 void calheight(char *r,int *sa,int n)
 53 {
 54      cls(rank);
 55      cls(height);
 56      int i,j,k=0;
 57 
 58      for(i=1;i<n;i++) rank[sa[i]]=i;
 59     // for(i=0;i<n;i++)  printf("%d ",rank[i]); putchar(10); system("pause");
 60 
 61      for(i=0;i<n;height[rank[i++]]=k)
 62          for(k?k--:0,j=sa[((rank[i]-1<0)?0:rank[i]-1)];r[i+k]==r[j+k]&&i!=j;k++);
 63      return;
 64 }
 65 
 66 char ca[maxn];
 67 int sa[maxn];
 68 int N;
 69 int minh[maxn];
 70 
 71 int main()
 72 {
 73     int i;
 74     while (~scanf("%s",ca))
 75     {
 76         N = strlen(ca);
 77         if(ca[0]=='.')   break;
 78         ca[N] = '#';
 79         N++;
 80         da(ca, sa, N, 130);
 81         calheight(ca,sa,N);
 82 
 83      //  for(i=0;i<N;i++)  cout<<rank[i]<<" "; cout<<endl;
 84      //   for(i=0;i<N;i++)  cout<<height[i]<<" "; cout<<endl;
 85 
 86      //   for(i=0;i<N;i++)  cout<<sa[i]<<" "; cout<<endl;
 87         int i;
 88         
 89         int mins = height[rank[0]];
 90         for(i=rank[0];i>0;i--)
 91         {
 92             if(mins>height[i])
 93             {
 94                 mins = height[i];
 95             }
 96             minh[i-1] = mins;
 97         }
 98         mins = height[rank[0]];
 99         for(i=rank[0];i<N;i++)
100         {
101             if(mins>height[i])
102             {
103                 mins = height[i];
104             }
105             minh[i] = mins;
106         }
107     
108          for (i=1;i<N;i++)
109          {
110             if ((N-1) % i==0&&minh[rank[i]]==N-1-i)
111             {
112                 printf("%d
",(N-1) / i);
113                 break;
114             }
115          }
116     }
117     return 0;
118 }