SA+LCP+RMQで任意の2つのsuffixの組について先頭何文字が一致しているかをlog(N)で求めることができる。
前処理も全部O(N)でやることもでき、高速。(下のコードはRMQの前処理がO(NlogN)だが)
HL分解した木に乗せることを考えながらライブラリ化した。
struct T {
ll v;
T(ll v = inf) : v(v) {}
T operator+(const T& t) { return T(min(v, t.v)); }
friend ostream& operator<<(ostream& out, const T& t) {
out << t.v; return out;
}
};
struct segtree{
int n; vector<T> seg;
void init(int mx) {
n = 1;
while(n < mx) n *= 2;
seg = vector<T>(n * 2);
}
segtree(int mx = 0) {
init(mx);
}
void update(int i, T x) {
i += n - 1;
seg[i] = x;
while(i > 0) {
i = (i - 1) / 2;
seg[i] = seg[i * 2 + 1] + seg[i * 2 + 2];
}
}
T ga(int a, int b, int k, int l, int r) {
if(b <= l || r <= a) return T();
if(a <= l && r <= b) return seg[k];
else {
T lv = ga(a, b, k * 2 + 1, l, (l + r) / 2);
T rv = ga(a, b, k * 2 + 2, (l + r) / 2, r);
return lv + rv;
}
}
void show() {
vector<T> tmp;
rep(i, 0, n) tmp.push_back(get(i, i + 1));
debug(tmp);
}
T get(int a, int b) { return ga(a, b, 0, 0, n); }
};
struct SA {
int n;
vi S, sa, rank, bkt;
vi lcp; segtree seg;
void init(const vi& sin, int K = 26) {
n = (int)sin.size();
S.resize(n + 1); rank.resize(n + 1);
rep(i, 0, n) S[i] = sin[i] + 1;
bkt.resize(max(n + 1, K + 1));
sa = get_sa(S, K + 1);
rep(i, 0, n + 1) rank[sa[i]] = i;
get_lcp();
seg.init(n);
rep(i, 0, n) seg.update(i, lcp[i]);
}
inline bool isLMS(const vi& t, int i) {
if(i > 0 && t[i] && !t[i - 1]) return true;
else return false;
}
void getBuckets(const vi& s, int K, bool end) {
int sum = 0, n = (int)s.size();
fill(bkt.begin(), bkt.begin() + K, 0);
rep(i, 0, n) bkt[s[i]]++;
rep(i, 0, K) {
sum += bkt[i];
bkt[i] = end ? sum : sum - bkt[i];
}
}
void induceSAl(const vi& t, const vi& s, vi& SA, int K) {
int n = (int)SA.size();
getBuckets(s, K, false);
rep(i, 0, n) {
int j = SA[i] - 1;
if(j >= 0 && !t[j]) SA[bkt[s[j]]++] = j;
}
}
void induceSAs(const vi& t, const vi& s, vi& SA, int K) {
int n = (int)SA.size();
getBuckets(s, K, true);
rer(i, n, 0) {
int j = SA[i] - 1;
if(j >= 0 && t[j]) SA[--bkt[s[j]]] = j;
}
}
vi get_sa(const vi& s, int K) {
int n = (int)s.size();
vi t(n, 0);
t[n - 1] = 1; t[n - 2] = 0;
rer(i, n - 2, 0)
if(s[i] < s[i + 1] || (s[i] == s[i + 1] && t[i + 1] == 1)) t[i] = 1;
getBuckets(s, K, true);
vi SA(n, -1);
rep(i, 1, n) if(isLMS(t, i)) SA[--bkt[s[i]]] = i;
induceSAl(t, s, SA, K); induceSAs(t, s, SA, K);
int n1 = 0;
rep(i, 0, n) if(isLMS(t, SA[i])) SA[n1++] = SA[i];
fill(SA.begin() + n1, SA.end(), -1);
int name = 0, prev = -1;
rep(i, 0, n1) {
int pos = SA[i]; bool diff = false;
rep(d, 0, n) {
if(prev == -1 || s[pos + d] != s[prev + d] || t[pos + d] != t[prev + d]) {
diff = true; break;
}
else if(d > 0 && (isLMS(t, pos + d) || isLMS(t, prev + d))) break;
}
if(diff) { name++; prev = pos; }
pos = (pos % 2 == 0) ? pos / 2 : (pos - 1) / 2;
SA[n1 + pos] = name - 1;
}
vi s1(n1, -1), SA1(n1, -1), p1(n1, -1);
int at = 0;
rep(i, n1, n) if(SA[i] >= 0) s1[at++] = SA[i];
if(name < n1) SA1 = get_sa(s1, name);
else rep(i, 0, n1) SA1[s1[i]] = i;
getBuckets(s, K, true);
at = 0;
rep(i, 1, n) if(isLMS(t, i)) p1[at++] = i;
fill(all(SA), -1);
rer(i, n1, 0) {
int j = p1[SA1[i]];
SA[--bkt[s[j]]] = j;
}
induceSAl(t, s, SA, K); induceSAs(t, s, SA, K);
return SA;
}
void get_lcp() {
lcp.resize(n);
int h = 0; lcp[0] = 0;
rep(i, 0, n) {
int j = sa[rank[i] - 1]; if(h > 0) h--;
while(j + h < n && i + h < n && S[j + h] == S[i + h]) h++;
lcp[rank[i] - 1] = h;
}
}
int common(int i, int j) {
if(i == j) return n - i;
else {
int a = rank[i], b = rank[j];
if(a > b) swap(a, b);
return seg.get(a, b).v;
}
}
};
sa.common(i,j)でsuffix(i)とsuffix(j)について求めることが出来る。
これを使うと色々面白いことが出来る。
まずはMP法と同じ配列を求めてみよう。
vi A(N + 1, -1);
rep(i, 1, N + 1) {
int c = sa.common(0, i);
rep(j, 0, c + 1) MAX(A[i + j], j);
}
suffix(0)とsuffix(i)がc文字一致していたら、suffix(0)とsuffix(i+j)はc-j文字一致していることを利用して求めている。
とてもシンプルだがO(N^2)。本家にはかなわない。
次は最長奇数回文
string rev = str; reverse(all(rev));
str = str + '{' + rev;
SA sa1; sa1.init(str_to_vec(str), 128);
rep(i, 0, N) {
int at = 2 * N - i;
debug(i, sa1.common(i, at) * 2 - 1);
}
真ん中の文字を決め打って、そこから何文字右方向と左方向に一致しているか見る。これはS=(元の文字列)+'{'+(反転させた文字列)についてSAをとればできる。最長偶数回文も同じようなことをすればできる。{は文字コード的にzの次なので便利。
KMPやMPは先頭とsuffix(i)が何文字一致しているかを求めるようなものだがSA+LCP+RMQなら任意の二つのsuffixについて求められる。
強い。(確信)
