AOJ 2644 Longest Match

,

別の問題の部分問題を解くlibraryのverifyとして解いた。

Longest Match

解説

suffix array + segment tree。

suffix arrayを用いれば、ある文字列$t$から始まる$s$の部分文字列の全体を、suffix array上の区間として$O(|t| \log |s|)$で取得できる。

後は、文字列$x$から始まる$s$の部分文字列の全体の中で最も左から始まるもの、 文字列$y$から始まる$s$の部分文字列の全体の中で最も右から始まるもの、が分かればよい。 これはsuffix array上のrange minimum queryおよびrange maximum queryであるので、単純なsegment treeで処理できる。

実装

segment treeは任意のmonoidで動く汎用なやつ。端の処理を丁寧にやれば半群に対応できるはず。

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
using namespace std;

vector<int> suffix_array(string const & s) { // O(nloglogn)
    int n = s.length();
    vector<int> sa(n+1);
    vector<int> rank(n+1);
    repeat (i,n+1) {
        sa[i] = i;
        rank[i] = i < n ? s[i] : -1;
    }
    for (int k = 1; k <= n; k *= 2) {
        auto compare = [&](int i, int j) {
            int ri = i + k <= n ? rank[i + k] : -1;
            int rj = j + k <= n ? rank[j + k] : -1;
            return make_pair(rank[i], ri) < make_pair(rank[j], rj);
        };
        sort(sa.begin(), sa.end(), compare);
        vector<int> dp(n+1);
        dp[sa[0]] = 0;
        repeat (i,n) dp[sa[i+1]] = dp[sa[i]] + compare(sa[i], sa[i+1]);
        rank = dp;
    }
    return sa;
}
int lower_bound(string const & s, vector<int> const & sa, string const & t) { // returns an index on suffix array
    int n = s.size();
    int l = 0, r = n+1;
    while (l + 1 < r) {
        int m = (l + r) / 2;
        (s.compare(sa[m], string::npos, t) < 0 ? l : r) = m;
    }
    return r;
}
int prefix_upper_bound(string const & s, vector<int> const & sa, string const & t) { // returns an index on suffix array
    int n = s.size();
    int l = 0, r = n+1;
    while (l + 1 < r) {
        int m = (l + r) / 2;
        (s.compare(sa[m], t.size(), t) <= 0 ? l : r) = m;
    }
    return r;
}

template <typename T>
struct segment_tree { // on monoid
    int n;
    vector<T> a;
    function<T (T,T)> append; // associative
    T unit;
    template <typename F>
    segment_tree(int a_n, T a_unit, F a_append) {
        n = pow(2,ceil(log2(a_n)));
        a.resize(2*n-1, a_unit);
        unit = a_unit;
        append = a_append;
    }
    void point_update(int i, T z) {
        a[i+n-1] = z;
        for (i = (i+n)/2; i > 0; i /= 2) {
            a[i-1] = append(a[2*i-1], a[2*i]);
        }
    }
    T range_concat(int l, int r) {
        return range_concat(0, 0, n, l, r);
    }
    T range_concat(int i, int il, int ir, int l, int r) {
        if (l <= il and ir <= r) {
            return a[i];
        } else if (ir <= l or r <= il) {
            return unit;
        } else {
            return append(
                    range_concat(2*i+1, il, (il+ir)/2, l, r),
                    range_concat(2*i+2, (il+ir)/2, ir, l, r));
        }
    }
};

int main() {
    string s; cin >> s;
    int n = s.size();
    vector<int> sa = suffix_array(s);
    segment_tree<int> xt(n+1, n+2, [](int a, int b) { return min(a,b); });
    segment_tree<int> yt(n+1,   0, [](int a, int b) { return max(a,b); });
    repeat (i,n+1) {
        xt.point_update(i, sa[i]);
        yt.point_update(i, sa[i]);
    }
    int m; cin >> m;
    repeat (i,m) {
        string x, y; cin >> x >> y;
        int xl = lower_bound(s, sa, x);
        int yl = lower_bound(s, sa, y);
        int xr = prefix_upper_bound(s, sa, x);
        int yr = prefix_upper_bound(s, sa, y);
        int l = xt.range_concat(xl, xr);
        int r = yt.range_concat(yl, yr);
        int ans = 0;
        if (xl < xr and yl < yr and l <= r and l + x.length() <= r + y.length()) {
            ans = max(ans, r + int(y.size()) - l);
        }
        cout << ans << endl;
    }
    return 0;
}