分享 超时 close code 代码 spa void src nbsp
POJ - 2406
kmp可以过的
学了sa就用sa搞一下,,一直TLE...
好像要用另外一种方法实现,还没学=_=
先放上超时的代码吧
- //#include <bits/stdc++.h>
- #include < iostream > #include < cstdio > #include < cstring > #include < algorithm > using namespace std;
- const int maxn = 1000010;
- char s[maxn];
- int sa[maxn],
- t1[maxn],
- t2[maxn],
- c[maxn];
- int h[maxn],
- rk[maxn];
- int n;
- void build_sa(int n, int m) {
- int i,
- *x = t1,
- *y = t2;
- for (i = 0; i < m; i++) c[i] = 0;
- for (i = 0; i < n; i++) c[x[i] = s[i]]++;
- for (i = 1; i < m; i++) c[i] += c[i - 1];
- for (i = n - 1; i >= 0; i--) sa[--c[x[i]]] = i;
- for (int k = 1; k <= n; k <<= 1) {
- int p = 0;
- for (i = n - k; i < n; i++) y[p++] = i;
- for (i = 0; i < n; i++) if (sa[i] >= k) y[p++] = sa[i] - k;
- for (i = 0; i < m; i++) c[i] = 0;
- for (i = 0; i < n; i++) c[x[y[i]]]++;
- for (i = 1; i < m; i++) c[i] += c[i - 1];
- for (i = n - 1; i >= 0; i--) sa[--c[x[y[i]]]] = y[i];
- swap(x, y);
- p = 1;
- x[sa[0]] = 0;
- for (i = 1; i < n; i++) x[sa[i]] = y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k] ? p - 1 : p++;
- if (p >= n) break;
- m = p;
- }
- }
- void geth(int n) {
- int i,
- j,
- k = 0;
- for (i = 0; i < n; i++) rk[sa[i]] = i;
- for (i = 0; i < n; i++) {
- if (k) k--;
- j = sa[rk[i] - 1];
- while (s[i + k] == s[j + k]) k++;
- h[rk[i]] = k;
- }
- }
- int main() {
- while (scanf("%s", s)) {
- if (s[0] == ‘.‘) break;
- int n = strlen(s) + 1; //!!!
- build_sa(n, 255);
- geth(n);
- int k;
- n--;
- for (k = 1; k <= n; k++) {
- if (n % k == 0 && h[rk[0]] == n - k) break;
- }
- printf("%d\n", n / k);
- }
- }
Power Strings POJ - 2406
来源: http://www.bubuko.com/infodetail-2351160.html