#include <bits/stdc++.h>
using namespace std;
const int N = 2e6 + 5;
char str[N];
int s[N], sa[N], rk[N], c[N], _x[N], _y[N];
int n,m;
/*
void Qsort(){
for (int i = 0; i <= m; i++) c[i] = 0;
for (int i = 1; i <= n; i++) c[x[i]]++;
for (int i = 1; i <= m; i++) c[i] += c[i - 1];
for (int i = n; i >= 1; i--) sa[c[x[y[i]]]--] = y[i];
}
*/
void SA() {
int *x = _x; //用陣列就超時，用指標就AC？
int *y = _y;
m = n;
for (int i = 0; i <= m; i++) c[i] = 0;
for (int i = 1; i <= n; i++) c[x[i] = s[i]]++;
for (int i = 1; i <= m; i++) c[i] += c[i - 1];
for (int i = n; i >= 1; i--) sa[c[x[i]]--] = i;
//for(int i=1;i<=n;i++) x[i]=s[i],y[i]=i;
//Qsort();
for (int k = 1, p; k <= n; k <<= 1,m=p) {
p = 0;
for (int i = n; i > n - k; i--) y[++p] = i;
for (int i = 1; i <= n; i++)
if (sa[i] > k)
y[++p] = sa[i] - k;
for (int i = 0; i <= m; i++) c[i] = 0;
for (int i = 1; i <= n; i++) c[x[i]]++;
for (int i = 1; i <= m; i++) c[i] += c[i - 1];
for (int i = n; i >= 1; i--) sa[c[x[y[i]]]--] = y[i];
p = y[sa[1]] = 1;
for (int i = 2, a, b; i <= n; i++) {
a = (sa[i] + k > n ? -1 : x[sa[i] + k]);
b = (sa[i - 1] + k > n ? -1 : x[sa[i - 1] + k]);
y[sa[i]] = (x[sa[i]] == x[sa[i - 1]] && a == b) ? p : ++p;
}
swap(x, y);
}
}
int main() {
while (~scanf("%d", &n)) {
scanf("%s", str + 1);
int pos[2] = {-1, -1};
for (int i = n; i >= 1; i--) {
if (~pos[str[i] - 'a'])
s[i] = n - (pos[str[i] - 'a'] - i);
else
s[i] = 0;
pos[str[i] - 'a'] = i;
}
SA();
for (int i = 1; i <= n; i++)
printf("%d ", sa[i]);
printf("\n");
}
return 0;
}
這里說的是SA() 里面的int *x,int *y ，如果在陣列外面直接開x[N],y[N] 就會超時,什么情況。TLE一天了。
uj5u.com熱心網友回復：
要是用陣列，不知道你陣列在哪里定義的，如果是在堆疊上的話，就超過堆疊空間大小了，使用指標就ac是什么意思？uj5u.com熱心網友回復：
大佬您好，就是int*x,int*y去掉然后用x[],y[]作為全域變數就會TLE，您看看是怎么回事uj5u.com熱心網友回復：
自學記憶體除錯。uj5u.com熱心網友回復：
打錯字了。斷點除錯，看記憶體。
把每一行的意思自己明確，從什么狀態變為什么狀態明確
uj5u.com熱心網友回復：
int *x = _x; //用陣列就超時，用指標就AC？
int *y = _y;
以上代碼，如果用陣列，就不能直接賦值了，要用回圈逐個元素賦值，所以會超時
uj5u.com熱心網友回復：
但是我直接在外面定義x[N],y[N],沒有賦值，不會增加時間啊，其他代碼都不改動。uj5u.com熱心網友回復：
把你的題目貼一下uj5u.com熱心網友回復：
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/29356.html
標籤：C++ 語言
上一篇：求教：如何開發自己的Just-In-Time Debugger？
下一篇：找師傅