后缀数组 UVA 11107 Life Forms

题目链接

题意：训练指南P223

分析：二分长度，把所有字符串连成一个字符串，中间用不同的字符分隔（这是为了保证匹配长度始终在一个字符串内）。height数组分段，vis数组标记哪些字符串被访问了，如果可行，更新长度最大值，以及所有符合条件的子串的起点，最后要按字典序从小到大输出。虽然写的有些搓，比LRJ慢几倍，其中还有RE，WA等错误，但是通过自己的思考与debug，终于AC还是很开心的。

#include <bits/stdc++.h>

const int N = 1001 * 100 + 5;
char s[N];
int sa[N], rank[N], height[N];
int ws[N], wa[N], wb[N];

bool cmp(int *r, int a, int b, int l) {
    return (r[a] == r[b] && r[a+l] == r[b+l]);
}
void DA(char *r, int n, int m = 128) {
    int i, j, p, *x = wa, *y = wb;
    for (i=0; i<m; ++i) ws[i] = 0;
    for (i=0; i<n; ++i) ws[x[i]=r[i]]++;
    for (i=1; i<m; ++i) ws[i] += ws[i-1];
    for (i=n-1; i>=0; --i) sa[--ws[x[i]]] = i;
    for (j=1, p=1; p<n; j<<=1, m=p) {
        for (p=0, i=n-j; i<n; ++i) y[p++] = i;
        for (i=0; i<n; ++i) if (sa[i] >= j) y[p++] = sa[i] - j;
        for (i=0; i<m; ++i) ws[i] = 0;
        for (i=0; i<n; ++i) ws[x[y[i]]]++;
        for (i=1; i<m; ++i) ws[i] += ws[i-1];
        for (i=n-1; i>=0; --i) sa[--ws[x[y[i]]]] = y[i];
        std::swap (x, y);
        for (p=1, x[sa[0]]=0, i=1; i<n; ++i) {
            x[sa[i]] = cmp (y, sa[i-1], sa[i], j) ? p - 1 : p++;
        }
    }
}
void calc_height(char *r, int *sa, int n) {
    int i, j, k = 0;
    for (i=1; i<=n; ++i) rank[sa[i]] = i;
    for (i=0; i<n; ++i) {
        if (k) k--;
        j = sa[rank[i]-1];
        while (r[i+k] == r[j+k]) k++;
        height[rank[i]] = k;
    }
}

std::vector<int> lens;
bool vis[105];
int m;

bool ok() {
    int ret = 0;
    for (int i=0; i<m; ++i) {
        if (vis[i]) {
            ret++;
        }
        if (ret > m / 2) {
            return true;
        }
    }
    return false;
}

bool check(int len, int n, std::vector<int> &fs) {
    bool flag = false, nex = true;
    int pos = -1;
    for (int i=1; i<=n; ++i) {
        if (s[sa[i-1]] == '$' || s[sa[i]] == '$') {
            continue;
        }
        if (height[i] >= len) {
            if (pos == -1) {
                memset (vis, false, sizeof (vis));
            }
            int loc = std::lower_bound (lens.begin (), lens.end (), sa[i-1]) - lens.begin ();
            vis[loc] = true;
            loc = std::lower_bound (lens.begin (), lens.end (), sa[i]) - lens.begin ();
            vis[loc] = true;
            pos = sa[i];
            if (nex && ok ()) {
                fs.push_back (pos);
                flag = true;
                nex = false;
            }
        } else {
            pos = -1;
            nex = true;
        }
    }
    return flag;
}

int main() {
    srand (time (NULL));
    int cas = 0;
    while (scanf ("%d", &m) == 1) {
        if (!m) {
            break;
        }
        if (cas++ > 0) {
            puts ("");
        }
        int n = 0;
        lens.clear ();
        for (int i=0; i<m; ++i) {
            scanf ("%s", s + n);
            n = strlen (s);
            lens.push_back (n);
            s[n++] = '$' + rand () % 10;
        }
        n--;
        DA (s, n + 1);
        calc_height (s, sa, n);
        int left = 1, right = n;
        std::vector<int> froms, fs;
        int best = 0;
        while (left <= right) {
            int mid = left + right >> 1;
            fs.clear ();
            if (check (mid, n, fs)) {
                if (best < mid) {
                    best = mid;
                    froms.clear ();
                    for (auto p: fs) {
                        froms.push_back (p);
                    }
                }
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        std::vector<std::string> ans;
        if (best > 0) {
            std::string tmp = "";
            for (int j=0; j<froms.size (); ++j) {
                int L = froms[j] + best;
                tmp = "";
                for (int i=froms[j]; i<L; ++i) {
                    //printf ("%c", s[i]);
                    tmp += s[i];
                }
                ans.push_back (tmp);
            }
            std::sort (ans.begin (), ans.end ());
            for (auto a: ans) {
                std::cout << a << '
';
            }
        } else {
            puts ("?");
        }
    }
    return 0;
}