Stammering Aliens 后缀数组、二分、二叉堆、ST表
Source
2009 South Western European Regional Contest
My Solution
题意:给出一个字符串,要求找出至少出现m次的最长子串长度。
后缀数组、二分、二叉堆、ST表
所求的就是相邻的m个后缀的LCP,即这m-1个height[i]的最小值,
所以可以二分答案,或者用ST表(O(nlogn)预处理,O(1)查询)来维护,或者用二叉堆也可以,这三种方法的运行速度依次降低。
1、后缀数组+二分
*#include
#include
#include
#include
#include
using namespace std;
typedef long long LL;
const int maxn = 4e4 + 8;
int sa[maxn], height[maxn];
int _rank[maxn], t1[maxn], t2[maxn], c[maxn];
string s;
inline void get_sa(const int &n, int m)
{
int i, k, *x = t1, *y = t2, p, j;
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(k = 1; k <= n; k <<= 1){
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-1]] == y[sa[i]] && y[sa[i-1]+k] == y[sa[i]+k]) ? p - 1 : p ++; if(p >= n) break;
m = p;
}
k = 0;
for(i = 0; i < n; i++) _rank[sa[i]] = i;
for(i = 0; i < n; i++){
if(k) --k; if(!_rank[i]) continue;
j = sa[_rank[i] - 1];
while(s[i + k] == s[j + k]) k++;
height[_rank[i]] = k;
}
}
inline void print(const int &n)
{
for(int i = 1; i <= n; i++){
//cout << i << " : " << height[i] << " " << sa[i] << endl;
for(int j = sa[i]; j < n; j++){
cout << s[j];
}
cout << endl;
}
cout << endl;
}
int Ind, t, m, n, cnt;
inline bool check(const int &x)
{
cnt = 1; t = sa[1];
for(int i = 2; i <= n; i++){ if(height[i] >= x){cnt++; t = max(t, sa[i]); }
else{cnt = 1; t = sa[i]; }
if(cnt >= m) Ind = max(Ind, t);
}
if(Ind != -1) return true;
else return false;
}
int main()
{
#ifdef LOCAL
freopen("6.in", "r", stdin);
//freopen("6.out", "w", stdout);
#endif // LOCAL
ios::sync_with_stdio(false); cin.tie(0);
int ansa, ansb, l, r, mid;
while(true){
cin >> m;
if(m == 0) break;
cin >> s;
n = s.size();
if(m == 1){cout << n << " " << 0 << endl; continue;}
get_sa(n+1, 256);
//print(n);
ansa = ansb = 0; l = 0, r = n + 1;
while(l + 1 < r){ mid = (l + r) >> 1; Ind = -1;
if(check(mid)){ansa = mid; ansb = Ind; l = mid; }
else r = mid;
}
if(ansa) cout << ansa << " " << ansb << endl; //! 0~n-1 based
else cout << "none" << endl;
}
return 0;
}
2、后缀数组+ST表
#include
#include
#include
#include
using namespace std;
typedef long long LL;
const int maxn = 4e4 + 8;
int sa[maxn], height[maxn];
int _rank[maxn], t1[maxn], t2[maxn], c[maxn];
string s;
inline void get_sa(const int &n, int m)
{
memset(t2, -1, sizeof t2);
int i, k, *x = t1, *y = t2, p, j;
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(k = 1; k <= n; k <<= 1){
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-1]] == y[sa[i]] && y[sa[i-1]+k] == y[sa[i]+k]) ? p - 1 : p ++; if(p >= n) break;
m = p;
}
k = 0;
for(i = 0; i < n; i++) _rank[sa[i]] = i;
for(i = 0; i < n; i++){
if(k) --k; if(!_rank[i]) continue;
j = sa[_rank[i] - 1];
while(s[i + k] == s[j + k]) k++;
height[_rank[i]] = k;
}
}
inline void print(const int &n)
{
for(int i = 0; i < n; i++){
for(int j = sa[i]; j < n; j++){
cout << s[j];
}
cout << endl;
}
cout << endl;
}
const int MAXN = 4e4 + 8;
struct ST_list{
int stTable[MAXN][32], preLog2[MAXN];
inline void st_prepare(const int &n, int arr[], const int &f){
preLog2[1] = 0;
for(int i = 2; i <= n; i++){
preLog2[i] = preLog2[i-1];
if((1 << (preLog2[i] + 1)) == i){ preLog2[i]++; } } for(int i = n - 1; i >= 0; i--){
stTable[i][0] = arr[i];
for(int j = 1; (i + (1 << j) - 1) < n; j++){
if(f)stTable[i][j] = min(stTable[i][j - 1], stTable[i + (1 << j - 1)][j - 1]);
else stTable[i][j] = max(stTable[i][j - 1], stTable[i + (1 << j - 1)][j - 1]);
}
}
}
inline int query_min(const int &l, const int &r, const int &f){
int len = r - l + 1, k = preLog2[len];
return f ? min(stTable[l][k], stTable[r - (1 << k) + 1][k]) : max(stTable[l][k], stTable[r - (1 << k) + 1][k]); } }sta, stb; int main() { #ifdef LOCAL freopen("6.in", "r", stdin); //freopen("6.out", "w", stdout); #endif // LOCAL //ios::sync_with_stdio(false); cin.tie(0); int m, n, i, ansa, ansb; while(true){ cin >> m;
if(m == 0) break;
cin >> s;
n = s.size();
if(m == 1){cout << n << " " << 0 << "n"; continue;}
get_sa(n+1, 256);
//print(n);
sta.st_prepare(n+1, height, 1); stb.st_prepare(n+1, sa, 0);
ansa = ansb = 0;
for(i = m; i <= n; i++){
if(ansa == sta.query_min(i - m + 2, i, 1)){
ansb = max(ansb, stb.query_min(i - m + 1, i, 0));
}
else if(ansa < sta.query_min(i - m + 2, i, 1)){
ansa = sta.query_min(i - m + 2, i, 1);
ansb = stb.query_min(i - m + 1, i, 0);
}
}
if(ansa) cout << ansa << " " << ansb << "n"; //! 0~n-1 based
else cout << "none" << "n";
}
return 0;
}
3、后缀数组+二叉堆
#include
#include
#include
#include
using namespace std;
typedef long long LL;
const int maxn = 4e5 + 8;
int sa[maxn], height[maxn];
int _rank[maxn], t1[maxn], t2[maxn], c[maxn];
string s;
inline void get_sa(const int &n, int m)
{
memset(t2, -1, sizeof t2);
int i, k, *x = t1, *y = t2, p, j;
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(k = 1; k <= n; k <<= 1){
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-1]] == y[sa[i]] && y[sa[i-1]+k] == y[sa[i]+k]) ? p - 1 : p ++; if(p >= n) break;
m = p;
}
k = 0;
for(i = 0; i < n; i++) _rank[sa[i]] = i;
for(i = 0; i < n; i++){
if(k) --k; if(!_rank[i]) continue;
j = sa[_rank[i] - 1];
while(s[i + k] == s[j + k]) k++;
height[_rank[i]] = k;
}
}
inline void print(const int &n)
{
for(int i = 0; i < n; i++){
for(int j = sa[i]; j < n; j++){
cout << s[j];
}
cout << endl;
}
cout << endl;
}
const int MAX_SIZE = 4e5 + 8;
const int INF_MIN = -1e9 - 8;
struct BinaryHeap{
int heap[MAX_SIZE], id[MAX_SIZE], pos[MAX_SIZE], n, counter;
void init(){
n = 0, counter = 0;
memset(heap, 0, sizeof heap);
memset(id, 0, sizeof id);
memset(pos,0, sizeof pos);
}
void push(const int &v){
heap[++n] = v;
id[n] = ++ counter;
pos[id[n]] = n;
up(n);
}
int top(){
return heap[1];
}
int pop(){
swap(heap[1], heap[n]);
swap(id[1], id[n--]);
pos[id[1]] = 1;
down(1);
return id[n+1];
//cout << id[n+1] << endl; } void _erase(int i){ heap[pos[i]] = INF_MIN; up(pos[i]); pop(); } void up(int i){ int x = heap[i], y = id[i]; for(int j = i / 2; j >= 1; j /= 2){
if(heap[j] > x){
heap[i] = heap[j];
id[i] = id[j];
pos[id[i]] = i;
i = j;
}
else{
break;
}
}
heap[i] = x;
id[i] = y;
pos[y] = i;
}
void down(int i){
int x = heap[i], y = id[i];
for(int j = i * 2; j <= n; j *= 2){
j += j < n && heap[j] > heap[j + 1];
if(heap[j] < x){ heap[i] = heap[j]; id[i] = id[j]; pos[id[i]] = i; i = j; } else{ break; } } heap[i] = x; id[i] = y; pos[y] = i; } }a, b; int main() { #ifdef LOCAL freopen("6.in", "r", stdin); //freopen("6.out", "w", stdout); #endif // LOCAL ios::sync_with_stdio(false); cin.tie(0); int m, n, i, ansa, ansb; while(true){ cin >> m;
if(m == 0) break;
cin >> s;
n = s.size();
if(m == 1){cout << n << " " << 0 << "n"; continue;}
get_sa(n+1, 256);
//print(n);
a.init(); b.init(); ansa = 0, ansb = 0; b.push(n - 1 - sa[1]);
for(i = 2; i <= m; i++) {a.push(height[i]); b.push(n - 1 - sa[i]);}
for(i = m+1; i <= n; i++){
if(ansa == a.top()){
ansb = max(ansb, n - 1 - b.top());
}
else if(ansa < a.top()){
ansa = a.top();
ansb = n - 1 - b.top();
}
a._erase(i - m); a.push(height[i]);
b._erase(i - m); b.push(n - 1 - sa[i]);
}
if(ansa == a.top()){
ansb = max(ansb, n - 1 - b.top());
}
else if(ansa < a.top()){
ansa = a.top();
ansb = n - 1 - b.top();
}
if(ansa) cout << ansa << " " << ansb << "n"; //! 0~n-1 based
else cout << "none" << "n";
}
return 0;
}
非特殊说明,本博所有文章均为博主原创,未经许可不得转载。
https://www.prolightsfxjh.com/
Thank you!
------from ProLightsfx
非特殊说明,本博所有文章均为博主原创,未经许可不得转载。
如经许可后转载,请注明出处:https://prolightsfxjh.com/article/poj-3882-stammering-aliens/
共有 0 条评论