HUID 5558 Alice's Classified Message 后缀数组+单调栈＋二分

http://acm.hdu.edu.cn/showproblem.php?pid=5558

对于每个后缀suffix(i)，想要在前面i - 1个suffix中找到一个pos，使得LCP最大。这样做O（n^2）

考虑到对于每一个suffix(i)，最长的LCP肯定在和他排名相近的地方取得。

按排名大小顺序枚举位置，按位置维护一个递增的单调栈，对于每一个进栈的元素，要算一算栈内元素和他的LCP最大是多少。

如果不需要输出最小的下标，最大的直接是LCP(suffix(st[top]), suffix(st[top - 1]))就是相邻的两个。

但是要求最小的下标，这样的话需要对整个栈进行一个遍历，找到下标最小的并且长度最大的。整个栈与新进来的栈顶元素的LCP存在单调性，单调递增，所以可以二分。

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cmath>

#include <algorithm>

#include <vector>

#include <queue>

#include <string>

#include <stack>

#include <map>

#include <set>

#include <bitset>

#define X first

#define Y second

#define clr(u,v); memset(u,v,sizeof(u));

#define in() freopen("data.txt","r",stdin);

#define out() freopen("ans","w",stdout);

#define Clear(Q); while (!Q.empty()) Q.pop();

#define pb push_back

#define inf (0x3f3f3f3f)

using namespace std;

typedef long long ll;

typedef pair<int, int> pii;

const int INF = 0x3f3f3f3f;

const int maxn =  + ;

int sa[maxn], x[maxn], y[maxn], book[maxn];

bool cmp(int r[], int a, int b, int len) {

    return r[a] == r[b] && r[a + len] == r[b + len];

}

void da(char str[], int sa[], int lenstr, int mx) {

    int *fir = x, *sec = y, *ToChange;

    for (int i = ; i <= mx; ++i) book[i] = ;

    for (int i = ; i <= lenstr; ++i) {

        fir[i] = str[i];

        book[str[i]]++;

    }

    for (int i = ; i <= mx; ++i) book[i] += book[i - ];

    for (int i = lenstr; i >= ; --i) sa[book[fir[i]]--] = i;

    for (int j = , p = ; p <= lenstr; j <<= , mx = p) {

        p = ;

        for (int i = lenstr - j + ; i <= lenstr; ++i) sec[++p] = i;

        for (int i = ; i <= lenstr; ++i) {

            if (sa[i] > j)

                sec[++p] = sa[i] - j;

        }

        for (int i = ; i <= mx; ++i) book[i] = ;

        for (int i = ; i <= lenstr; ++i) book[fir[sec[i]]]++;

        for (int i = ; i <= mx; ++i) book[i] += book[i - ];

        for (int i = lenstr; i >= ; --i) sa[book[fir[sec[i]]]--] = sec[i];

//        ToChange = fir, fir = sec, sec = ToChange;

        swap(fir, sec);

        fir[sa[]] = ;

        p = ;

        for (int i = ; i <= lenstr; ++i) {

            fir[sa[i]] = cmp(sec, sa[i - ], sa[i], j) ? p -  : p++;

        }

    }

}

int height[maxn], RANK[maxn];

void calcHight(char str[], int sa[], int lenstr) {

    for (int i = ; i <= lenstr; ++i) RANK[sa[i]] = i;

    int k = ;

    for (int i = ; i <= lenstr - ; ++i) {

        k -= k > ;

        int j = sa[RANK[i] - ];

        while (str[j + k] == str[i + k]) ++k;

        height[RANK[i]] = k;

    }

}

char str[maxn];

int dp[maxn][];

vector<int> fuck[];

const int need = ;

void init_RMQ(int n, int a[]) {

    for (int i = ; i <= n; ++i) {

        dp[i][] = a[i];

    }

    for (int j = ; j < need; ++j) {

        for (int i = ; i + ( << j) -  <= n; ++i) {

            dp[i][j] = min(dp[i][j - ], dp[i + ( << (j - ))][j - ]);

        }

    }

}

int ask(int be, int en) {

    if (be > en) swap(be, en);

    be++;

    int k = (int)log2(en - be + );

    return min(dp[be][k], dp[en - ( << k) + ][k]);

}

int f;

int st[maxn], top;

int t[maxn];

int ans[maxn], id[maxn];

bool check(int pos, int len) {

    int res = ask(RANK[st[pos]], RANK[st[top]]);

    return res == len;

}

void work() {

    memset(ans, , sizeof ans);

    memset(id, 0x3f, sizeof id);

    scanf("%s", str + );

    int lenstr = strlen(str + );

    str[lenstr + ] = '$';

    str[lenstr + ] = '\0';

    da(str, sa, lenstr + , );

    calcHight(str, sa, lenstr + );

//    for (int i = 1; i <= lenstr + 1; ++i) {

//        printf("%d ", sa[i]);

//    }

//    printf("\n");

    init_RMQ(lenstr + , height);

    printf("Case #%d:\n", ++f);

    top = ;

    for (int i = ; i <= lenstr + ; ++i) {

        while (top >=  && sa[i] < st[top]) {

            top--;

        }

        st[++top] = sa[i];

        if (top >= ) {

            int tlen = ask(RANK[st[top]], RANK[st[top - ]]);

            ans[st[top]] = tlen;

            id[st[top]] = st[top - ];

            int be = , en = top - ;

            while (be <= en) {

                int mid = (be + en) >> ;

                if (check(mid, tlen)) en = mid - ;

                else be = mid + ;

            }

            id[st[top]] = st[be];

        }

    }

//    for (int i = 1; i <= lenstr; ++i) {

//        printf("%d ", ans[i]);

//    }

//    printf("\n");

    top = ;

    for (int i = lenstr + ; i >= ; --i) {

        while (top >=  && sa[i] < st[top]) {

            top--;

        }

        st[++top] = sa[i];

        if (top >= ) {

            int tlen = ask(RANK[st[top]], RANK[st[top - ]]);

            if (ans[st[top]] < tlen) {

                ans[st[top]] = tlen;

                id[st[top]] = st[top - ];

            } else if (ans[st[top]] == tlen && id[st[top]] > st[top - ]) {

                id[st[top]] = st[top - ];

            } else if (ans[st[top]] > tlen) continue; // 太小了

            int be = , en = top - ;

            while (be <= en) {

                int mid = (be + en) >> ;

                if (check(mid, tlen)) en = mid - ;

                else be = mid + ;

            }

            if (check(be, tlen))

                id[st[top]] = min(id[st[top]], st[be]);

        }

    }

//    for (int i = 1; i <= lenstr; ++i) {

//        printf("%d ", ans[i]);

//    }

//    printf("\n");

    for (int i = ; i <= lenstr;) {

        if (ans[i] == ) {

            printf("%d %d\n", -, str[i]);

            i++;

        } else {

            printf("%d %d\n", ans[i], id[i] - );

            i += ans[i];

        }

    }

}

int main()

{

#ifdef local

    in();

#else

#endif

//    printf("%d\n", 1 << 17);

    int t;

    scanf("%d", &t);

    while (t--) work();

    return ;

}

或者直接sam一波，sam的建立是在线的，可以不断更新不断弄。

#include <bits/stdc++.h>

#define IOS ios::sync_with_stdio(false)

using namespace std;

#define inf (0x3f3f3f3f)

typedef long long int LL;

const int N = ;

const int maxn =  + ;

struct Node {

    int cnt, id, pos; // cnt表示在后缀自动机中从root走到它最多需要多少步

    //id表示它是第几个后缀自动机节点，指向了它，但是不知道是第几个，需要id判断

    //pos表示它在原串中的位置。

    struct Node *pNext[N], *fa;

}suffixAutomaon[maxn * ], *root, *last; //大小需要开2倍，因为有一些虚拟节点

int t; // 用到第几个节点

struct Node *create(int cnt = -, struct Node *node = NULL) { //新的节点

    if (cnt != -) {

        suffixAutomaon[t].cnt = cnt, suffixAutomaon[t].fa = NULL;

        suffixAutomaon[t].id = t;

        for (int i = ; i < N; ++i) suffixAutomaon[t].pNext[i] = NULL;

    } else {

        suffixAutomaon[t] = *node; //保留了node节点指向的信息

        suffixAutomaon[t].id = t; //必须要有的，不然id错误

        //可能需要注意下pos，在原串中的位置。

//        suffixAutomaon[t].pos = su

    }

    return &suffixAutomaon[t++];

}

void init() {

    t = ;

    root = last = create(, NULL);

}

void addChar(int x, int pos) { //pos表示在原串的位置

    struct Node *p = last, *np = create(p->cnt + , NULL);

    np->pos = pos, last = np; //最后一个可接收后缀字符的点。

    for (; p != NULL && p->pNext[x] == NULL; p = p->fa) p->pNext[x] = np;

    if (p == NULL) {

        np->fa = root;

        return;

    }

    struct Node *q = p->pNext[x];

    if (q->cnt == p->cnt + ) { //中间没有任何字符

        np->fa = q;

        return;

    }

//    p：指向的可以接受后缀的节点

//    np:当前插入字符x的新节点

//    q：q = p->pNext[x]，q就是p中指向的x字符的节点

//    nq:因为q->cnt != p->cnt + 1而新建出来的模拟q的节点

    struct Node *nq = create(-, q); // 新的q节点，用来代替q，帮助np接收后缀字符

    nq->cnt = p->cnt + ; //就是需要这样，这样中间不包含任何字符

    q->fa = nq, np->fa = nq; //现在nq是包含了本来q的所有指向信息

    for (; p && p->pNext[x] == q; p = p->fa) {

        p->pNext[x] = nq;

    }

}

void build(char str[], int lenstr) {

    init();

    for (int i = ; i <= lenstr; ++i) addChar(str[i] - 'a', i);

}

char str[maxn];

int f;

void work() {

    scanf("%s", str + );

    int lenstr = strlen(str + );

    printf("Case #%d:\n", ++f);

    init();

    for (int i = ; i <= lenstr;) {

        int now = , len = ;

        for (; i <= lenstr && suffixAutomaon[now].pNext[str[i] - 'a']; ++i, ++len) {

            now = suffixAutomaon[now].pNext[str[i] - 'a']->id;

            addChar(str[i] - 'a', i);

        }

        if (len) {

            printf("%d %d\n", len, suffixAutomaon[now].pos - len);

        } else {

            printf("-1 %d\n", str[i]);

            addChar(str[i] - 'a', i);

            i++;

        }

    }

}

int main() {

#ifdef local

    freopen("data.txt", "r", stdin);

//    freopen("data.txt", "w", stdout);

#endif

    int t;

    scanf("%d", &t);

    while (t--) work();

    return ;

}

巴特西

HUID 5558 Alice's Classified Message 后缀数组+单调栈＋二分

最新文章

热门文章