POJ – 3882 Stammering Aliens 后缀数组、二分、二叉堆、ST表

ProLightsfx 2017-2-17 176 2/17

Stammering Aliens 后缀数组、二分、二叉堆、ST表

 Source

POJ - 3882

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

- THE END -

ProLightsfx

11月15日18:47

最后修改:2024年11月15日
0

非特殊说明,本博所有文章均为博主原创,未经许可不得转载。

共有 0 条评论