SA+LCP+RMQ

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について求められる。
強い。(確信)