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); } //edit from here T get(int a, int b) { return ga(a, b, 0, 0, n); } //[a, b) }; struct SA { //get_sa: don't forget to specify K. default:26 int n; vi S, sa, rank, bkt; //i in S is rank[i] in sa 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(); //if you don't want lcp, comment out seg.init(n); //if you don't want seg, comment out 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について求められる。
強い。(確信)