| Time Limit: 1000MS | Memory Limit: 65536K | |
| Total Submissions: 13195 | Accepted: 4077 |
Description
The repetition number of a string is defined as the maximum number R such that the string can be partitioned into R same consecutive substrings. For example, the repetition number of "ababab" is 3 and "ababa" is 1.
Given a string containing lowercase letters, you are to find a substring of it with maximum repetition number.
Input
The input consists of multiple test cases. Each test case contains exactly one line, which
gives a non-empty string consisting of lowercase letters. The length of the string will not be greater than 100,000.
The last test case is followed by a line containing a '#'.
Output
For each test case, print a line containing the test case number( beginning with 1) followed by the substring of maximum repetition number. If there are multiple substrings of maximum repetition number, print the lexicographically smallest one.
Sample Input
ccabababc daabbccaa #
Sample Output
Case 1: ababab Case 2: aa
【题目大意】
找到 n 个子串中，重复次数最多的字符串，如果重复次数相同，输出字典序最小的那个
【题目分析】
【代码】
1 #include<cstdio> 2 #include<cstring> 3 #include<string> 4 #include<iostream> 5 #include<algorithm> 6 using namespace std; 7 const int MAX_CHAR = 128; 8 const int MAXN = 100000 + 5; 9 const int INF = 2e9 + 7; 10 int lg[MAXN], f[MAXN], g[MAXN]; 11 struct suff_string 12 { 13 int n, m; 14 int x[MAXN] , y[MAXN] , c[MAXN] ; 15 int SA[MAXN], rak[MAXN], height[MAXN]; 16 int st[17][MAXN]; 17 void build_SA(char *s) 18 { 19 n = strlen(s + 1); 20 m = MAX_CHAR; 21 for (int i = 1; i <= 100000; i++) 22 x[i] = y[i] = c[i] = SA[i]=rak[i]=height[i]=0; 23 for (int i = 1; i <= n; i++) 24 SA[i] = rak[i] = height[i] = 0; 25 for (int i = 1; i <= n; i++) 26 ++c[x[i] = s[i]]; 27 for (int i = 2; i <= m; i++) 28 c[i] += c[i - 1]; 29 for (int i = n; i >= 1; i--) 30 SA[c[x[i]]--] = i; 31 for (int k = 1; k <= n; k <<= 1) 32 { 33 int num = 0; 34 for (int i = n - k + 1; i <= n; i++) y[++num] = i; 35 for (int i = 1; i <= n; i++) 36 if (SA[i] > k) 37 y[++num] = SA[i] - k; 38 for (int i = 1; i <= m; i++) 39 c[i] = 0; 40 for (int i = 1; i <= n; i++) 41 c[x[i]]++; 42 for (int i = 2; i <= m; i++) 43 c[i] += c[i - 1]; 44 for (int i = n; i >= 1; i--) 45 SA[c[x[y[i]]]--] = y[i], y[i] = 0; 46 swap(x, y); 47 x[SA[1]] = 1; num = 1; 48 for (int i = 2; i <= n; i++) 49 x[SA[i]] = (y[SA[i]] == y[SA[i - 1]] && y[SA[i] + k] == y[SA[i - 1] + k]) ? num : ++num; 50 if (num == n) break; 51 m = num; 52 } 53 for (int i = 1; i <= n; i++) 54 rak[SA[i]] = i; 55 return; 56 } 57 void get_height(char *s) 58 { 59 int k = 0; 60 for (int i = 1; i <= n; i++) { 61 if (k) k--; 62 int j = SA[rak[i] - 1]; 63 while (i + k <= n && j + k <= n && s[i + k] == s[j + k]) k++; 64 height[rak[i]] = k; 65 } 66 } 67 68 void build_ST() 69 { 70 memset(st, 0, sizeof(st)); 71 for (int i = 1; i <= n; i++) 72 st[0][i] = height[i]; 73 for (int i = 1; i <= 16; i++) 74 for (int j = 1; j <= n; j++) 75 st[i][j] = min(st[i - 1][j], st[i - 1][j + (1 << (i - 1))]); 76 } 77 int query(int l, int r) 78 { 79 l = rak[l], r = rak[r]; 80 if (l > r) swap(l, r); l++; 81 int t = lg[r + 1 - l]; 82 return min(st[t][l], st[t][r - (1 << t) + 1]); 83 } 84 }A; 85 char s[MAXN]; 86 int _ = 0; 87 int ans[MAXN]; 88 bool solve() 89 { 90 scanf("%s", s + 1); 91 if (s[1] == '#') 92 return 0; 93 A.build_SA(s); A.get_height(s); A.build_ST(); 94 int n = A.n; 95 int mx = -1; 96 int len = 0; 97 for (int i = 1; i < n; i++) 98 { 99 for (int j = 1; j+i <= n; j += i) 100 { 101 int k = A.query(j,j+i); 102 int t = k / i +1; 103 int left = i - (k%i); 104 int head =j- left; 105 if (head >= 1 && A.query(head, head + i)>=left) t++; 106 if (t > mx) 107 { 108 mx = t; 109 ans[0] = 0; 110 } 111 if (t == mx) 112 { 113 ans[++ans[0]] = i; 114 } 115 } 116 } 117 int head=INF; 118 int flag = 0; 119 for (int i = 1; i <= n; i++) 120 { 121 for (int j = 1; j <= ans[0]; j++) 122 { 123 int l = ans[j]; 124 if (A.query(A.SA[i], A.SA[i] + l) >= (mx - 1)*l) 125 { 126 len = l; 127 head = A.SA[i]; 128 flag = 1; 129 break; 130 } 131 } 132 if (flag) break; 133 } 134 printf("Case %d: ", ++_); 135 for (int i = 0; i <mx*len; i++) 136 printf("%c", s[head+i]); 137 printf("\n"); 138 return 1; 139 } 140 int main() 141 { 142 int T; 143 for (int i = 2; i <= 100000; i++) lg[i] = lg[i >> 1] + 1; 144 scanf("%d", &T); 145 getchar(); 146 while (T-- && solve()) 147 { 148 149 } 150 return 0; 151 }