题目描述： 找出一个字符串中至少重复出现两次的字串的个数（重复出现时不能重叠）。
code:
后缀数组处理，对于得到height 进行查找... 参考http://blog.csdn.net/mishifangxiangdefeng/article/details/7109211博主的详细的代码思路
代码语言：javascript复制 1 #include<iostream>
2 #include<string>
3 using namespace std;
4 #define N 1200
5 string s;
6 int n, sa[4*N], rank[N], height[N];
7 int buf[4*N], ct[N], sx[N], sax[N];
8 inline bool leq(int a, int b, int x, int y)
9 {
10 return (a < x || a == x && b <= y);
11 }
12 inline bool leq(int a, int b, int c, int x, int y, int z)
13 {
14 return (a < x || a == x && leq(b, c, y, z));
15 }
16 inline int geti(int t, int nx, int sa[])
17 {
18 return (sa[t]<nx ? sa[t]*3 1 : (sa[t]-nx)*3 2);
19 }
20 //基数排序
21 static void radix(int a[], int b[], int s[], int n, int k)
22 { // sort a[0..n-1] to b[0..n-1] with keys in 0..k from s
23 int i, t, sum;
24 memset(ct, 0, (k 1) * sizeof(int));
25 for (i = 0; i < n; i) ct[s[a[i]]] ;
26 for (i = 0, sum = 0; i <= k; i)
27 {
28 t = ct[i]; ct[i] = sum; sum = t;
29 }
30 for (i = 0; i < n; i ) b[ct[s[a[i]]] ] = a[i];
31 }
32
33 /*
34 倍增算法,构造后缀数组的最坏时间复杂度为O(nlogn)。
35 参数：
36 int *r：待排序的字符串放在 r 数组中 ， 从 r[0] 到 r[n-1] ， 长度为 n ， 且最大值小于 m 。
37 为了函数操作的方便，约定除r[n-1] 外所有的 r[i] 都大于 0, r[n-1]=0 。
38 int *sa：函数结束后，结果放在 sa 数组中，从 sa[0] 到 sa[n-1] 。
39 */
40 void suffix(int s[], int sa[], int n, int k)
41 { // !!! require s[n] = s[n 1] = s[n 2] = 0, n >= 2.
42 int i, j, e, p, t;
43 int name = 0, cx = -1, cy = -1, cz = -1;
44 int nx = (n 2)/3, ny = (n 1)/3, nz = n/3, nxz = nx nz;
45 int *syz = s n 3, *sayz = sa n 3;
46 for (i=0, j=0; i < n (nx - ny); i )
47 if (i%3 != 0) syz[j ] = i;
48 radix(syz , sayz, s 2, nxz, k);
49 radix(sayz, syz , s 1, nxz, k);
50 radix(syz , sayz, s , nxz, k);
51 for (i = 0; i < nxz; i )
52 {
53 if (s[ sayz[i] ] != cx || s[ sayz[i] 1 ] != cy ||s[ sayz[i] 2 ] != cz)
54 {
55 name ; cx = s[ sayz[i] ];
56 cy = s[ sayz[i] 1 ]; cz = s[ sayz[i] 2 ];
57 }
58 if (sayz[i] % 3 == 1) syz[ sayz[i] / 3 ] = name;
59 else syz[ sayz[i]/3 nx ] = name;
60 }
61 if (name < nxz)
62 {
63 suffix(syz, sayz, nxz, name);
64 for (i = 0; i < nxz; i ) syz[sayz[i]] = i 1;
65 }
66 else
67 {
68 for (i = 0; i < nxz; i ) sayz[syz[i] - 1] = i;
69 }
70 for (i = j = 0; i < nxz; i )
71 if (sayz[i] < nx) sx[j ] = 3 * sayz[i];
72 radix(sx, sax, s, nx, k);
73 for (p=0, t=nx-ny, e=0; e < n; e )
74 {
75 i = geti(t, nx, sayz); j = sax[p];
76 if ( sayz[t] < nx ?leq(s[i], syz[sayz[t] nx], s[j], syz[j/3]) :
77 leq(s[i], s[i 1], syz[sayz[t]-nx 1],
78 s[j], s[j 1], syz[j/3 nx]) )
79 {
80 sa[e] = i;
81 if ( t == nxz)
82 {
83 for (e ; p < nx; p , e )
84 sa[e] = sax[p];
85 }
86 }
87 else
88 {
89 sa[e] = j;
90 if ( p == nx) for ( e; t < nxz; t, e)
91 sa[e] = geti(t, nx, sayz);
92 }
93 }
94 }
95
96 /*
97 后缀数组 SA 是一个一维数组，它保存 1..n 的某个排列SA[1]，SA[2]，……，SA[n]，
98 并且保证 Suffix(SA[i]) < Suffix(SA[i 1]) ， 1 ≤ i<n 。
99 也就是将 S 的 n 个后缀从小到大进行排序之后把排好序的后缀的开头位置顺次放入 SA 中。
100 */
101 void makesa()
102 {
103 memset(buf, 0, 4 * n * sizeof(int));
104 memset(sa, 0, 4 * n * sizeof(int));
105 for (int i=0; i<n; i) buf[i] = s[i] & 0xff;
106 suffix(buf, sa, n, 255);
107 }
108
109
110
111 /*
112 名次数组 Rank[i] 保存的是 Suffix(i) 在所有后缀中从小到大 排列的 “ 名次 ” 。
113 容易看出，后缀数组和名次数组为互逆运算。
114 设字符串的长度为 n 。
115 为了方便比较大小，可以在字符串后面添加一个字符，这个字符没有在前面的字符中出现过，而且比前面的字符都要小。
116 在求出名次数组后，可以仅用 O(1) 的时间比较任意两个后缀的大小。
117 在求出后缀数组或名次数组中的其中一个以后，便可以用 O(n) 的时间求出另外一个。
118 任意两个后缀如果直接比较大小，最多需要比较字符 n 次，也就是说最迟在比较第 n 个字符时一定能分出 “ 胜负 ” 。
119 */
120 void getRank()
121 {
122 for(int i = 1;i < n; i)
123 rank[sa[i]] = i;
124 }
125 /*
126 对两个字符串u,v定义函数lcp(u,v)=max{i|u=iv}，也就是从头开始顺次比较u和v的对应字符，对应字符持续相等的最大位置，
127 称为这两个字符串的最长公共前缀。
128 对正整数i,j定义LCP(i,j)=lcp(Suffix(SA[i]),Suffix(SA[j]))，其中i,j均为1至n的整数。LCP(i,j)也就是后缀数组中第i个
129 和第j个后缀的最长公共前缀的长度。
130 定义一维数组height，令height[i]=LCP(i-1,i)，1<i≤n，并设height[1]=0。
131 */
132 void lcp()
133 { // O(4 * N)
134 int i, j, k;
135 for (j = rank[height[i=k=0]=0]; i < n - 1; i , k )
136 while (k >= 0 && s[i] != s[ sa[j-1] k ])
137 height[j] = (k--), j = rank[ sa[j] 1 ];
138 }
139 int main()
140 {
141
142 while(cin>>s && s[0] != '#')
143 {
144 n = s.length() 1;
145 makesa();
146 getRank();
147 lcp();
148 int ans = 0, minid, maxid;
149 //枚举字串长度h
150 for(int i = 1; i <= (n >> 1); i )
151 {
152 minid = 1200, maxid = -1;
153 //对于每一次的h，利用height数组，找出连续的height大于等于h的里面最左端和最右端得为之l和r。
154 for(int j = 2; j < n; j )
155 if (height[j] >= i)
156 {
157 if (sa[j - 1] < minid) minid = sa[j - 1];
158 if (sa[j - 1] > maxid) maxid = sa[j - 1];
159 if (sa[j] < minid) minid = sa[j];
160 if (sa[j] > maxid) maxid = sa[j];
161 }
162 else
163 {
164 //如果l h - 1 < r的话，说明没有重叠，答案加1.
165 if (maxid != -1 && minid i <= maxid) ans ;
166 minid = 1200, maxid = -1;
167 }
168 //如果l h - 1 < r的话，说明没有重叠，答案加1.
169 if (maxid != -1 && minid i <= maxid) ans ;
170 }
171 cout<<ans<<endl;
172 }
173 return 0;
174 }
