[BZOJ5417/UOJ#395/NOI2018]你的名字（字尾自動機+主席樹）

Address

洛谷P4770

BZOJ5417

UOJ#395

Solution…

68pts： l = 1 , r = ∣ S ∣ l=1,r=|S| l=1,r=∣S∣

建議先做：[BZOJ4566][Haoi2016]找相同字元

詢問前先建出 S S S 的字尾自動機，然後求出 T T T 的每個字首 T [ 1... i ] T[1...i] T[1...i] 的字尾最多能在 S S S 中比對多長。也就是說，我們需要對于每個 i i i 求出一個最大的 m x [ i ] = j mx[i]=j mx[i]=j ，使得 T [ i − j + 1... i ] T[i-j+1...i] T[i−j+1...i] 在 S S S 中出現過。那麼顯然這樣對答案的貢獻為 i − j i-j i−j 。 j j j 可以用在字尾自動機上走轉移邊和 Parent 邊得到，類似于求最長公共子串的方法。

但我們要統計的是 T T T 本質不同的子串，是以我們想辦法讓已經出現過的子串不被統計。是以建出 T T T 的字尾自動機。同樣地，可以「自己和自己比對」，求出一個最大的 n x t [ i ] = j nxt[i]=j nxt[i]=j 滿足 T [ i − j + 1... i ] T[i-j+1...i] T[i−j+1...i] 是 T [ 1... i − 1 ] T[1...i-1] T[1...i−1] 的子串，那麼這樣左端點在 [ n x t [ i ] , i ] [nxt[i],i] [nxt[i],i] 而右端點為 i i i 的子串不會被再次統計。

那麼這次詢問的答案為：

∑ i = 1 ∣ T ∣ { i − max ⁡ ( n x t [ i ] , m x [ i ] ) } \sum_{i=1}^{|T|}\{i-\max(nxt[i],mx[i])\} i=1∑∣T∣​{i−max(nxt[i],mx[i])}

複雜度 O ( ∣ S ∣ + ∑ ∣ T ∣ ) O(|S|+\sum|T|) O(∣S∣+∑∣T∣) 。期望得分 68 68 68 分。

100pts： 1 ≤ l ≤ r ≤ ∣ S ∣ 1\le l\le r\le |S| 1≤l≤r≤∣S∣

求 n x t [ i ] nxt[i] nxt[i] 還是一樣。而關鍵在于求 m x [ i ] mx[i] mx[i] 。

假設我們已經求得了 m x [ i − 1 ] mx[i-1] mx[i−1] 并且走到了 S S S 的字尾自動機上的節點 u u u 。

先考慮一個小問題：

如何判斷狀态 u u u （不是初始狀态）所能夠表示出的所有長度為 k k k 的子串中，是否存在一個出現在 S [ l . . . r ] S[l...r] S[l...r] 内。

問題等價于求 u u u 的 R i g h t Right Right 集合中是否存在一個數在 [ l + k − 1 , r ] [l+k-1,r] [l+k−1,r] 範圍内。

我們知道，如果在建構 S S S 的過程中将拆解出的所有點設為白點，其他點（初始狀态除外）為黑點，那麼點 u u u 的 R i g h t Right Right 集合就是 u u u 的 Parent 子樹内所有黑點。

于是轉化為求 u u u 的 Parent 子樹中是否存在一個黑點的 M a x l Maxl Maxl 在 [ l + k − 1 , r ] [l+k-1,r] [l+k−1,r] 範圍内。

求出 Parent 樹的 DFS 序列之後，可以用主席樹求得。

回到原問題。考慮如何判斷狀态 u u u 表示出的所有 S S S 的子串是否存在一個子串包含于 [ l , r ] [l,r] [l,r] 。如果沒有則需要把 u u u 往 Parent 跳直到存在或者跳回初始狀态為止。

易得，我們要求的是 u u u 的 Parent 子樹内， M a x l Maxl Maxl 在 [ l , r ] [l,r] [l,r] 範圍内并且最大的值。

仍然可以使用主席樹查這個值。

這樣我們就能得到狀态 u u u 在 S [ l . . . r ] S[l...r] S[l...r] 内能夠比對的最長子串。

（注：黑點的 M a x l Maxl Maxl 的另一個含義是：這個點表示出的子串之一為 S S S 的長度為 M a x l Maxl Maxl 的字首。故 u u u 的 R i g h t Right Right 集合實際上是 u u u 的 Parent 子樹内所有黑點的 M a x l Maxl Maxl 組成的集合）

具體實作：求得 m x [ i − 1 ] mx[i-1] mx[i−1] 以及到達的 S S S 中的點 u u u ，設 c = T [ i ] c=T[i] c=T[i] 。

如果以下兩條件都滿足：

（1） u u u 有字元 c c c 的轉移邊。設 u u u 通過字元 c c c 轉到 v v v 。

（2） v v v 在 S [ l . . . r ] S[l...r] S[l...r] 内能比對到子串，設最長長度為 l l l 。

就将 u u u 通過字元 c c c 邊轉移，并把 m x [ i ] mx[i] mx[i] 設成 l l l 。

否則将 u u u 跳到 Parent 繼續判斷。

裆燃，如果 u u u 跳到了根就直接退出。

Code

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define For(i, a, b) for (i = a; i <= b; i++)
#define Rof(i, a, b) for (i = a; i >= b; i--)
#define SAM_AS(i, z) for (; i && z; i = AS[i].fa)
#define SAM_AT(i, z) for (; i && z; i = AT[i].fa)
#define Edge(u) for (int e = adj[u], v = go[e]; e; e = nxt[e], v = go[e])
using namespace std;

inline int read()
{
	int res = 0; bool bo = 0; char c;
	while (((c = getchar()) < '0' || c > '9') && c != '-');
	if (c == '-') bo = 1; else res = c - 48;
	while ((c = getchar()) >= '0' && c <= '9')
		res = (res << 3) + (res << 1) + (c - 48);
	return bo ? ~res + 1 : res;
}

template <class T>
T Max(T a, T b) {return a > b ? a : b;}

template <class T>
T Min(T a, T b) {return a < b ? a : b;}

typedef long long ll;
const int N = 5e5 + 5, M = N << 1, L = 3e7 + 5;

int n, m, q, lst, ToT, QAQ, w[N], tmp[M], ecnt, nxt[M], adj[M], go[M],
rt[M], QwQ, dfn[M], sze[M], TAT, a[M];
char S[N], T[N];

void add_edge(int u, int v)
{
	nxt[++ecnt] = adj[u]; adj[u] = ecnt; go[ecnt] = v;
}

struct node
{
	int fa, go[26], maxl, ri;
	void init()
	{
		fa = maxl = ri = 0;
		memset(go, 0, sizeof(go));
	}
} AS[M], AT[M];

struct seg
{
	int lc, rc, sum;
} Tr[L];

void ins(int y, int &x, int l, int r, int p)
{
	Tr[x = ++TAT] = Tr[y]; Tr[x].sum++;
	if (l == r) return;
	int mid = l + r >> 1;
	if (p <= mid) ins(Tr[y].lc, Tr[x].lc, l, mid, p);
	else ins(Tr[y].rc, Tr[x].rc, mid + 1, r, p);
}

int querysum(int y, int x, int l, int r, int up)
{
	if (l == r) return Tr[x].sum - Tr[y].sum;
	int mid = l + r >> 1;
	if (up <= mid) return querysum(Tr[y].lc, Tr[x].lc, l, mid, up);
	else return Tr[Tr[x].lc].sum - Tr[Tr[y].lc].sum
		+ querysum(Tr[y].rc, Tr[x].rc, mid + 1, r, up);
}

int squery(int y, int x, int l, int r, int sum)
{
	if (l == r) return l;
	int mid = l + r >> 1, delta = Tr[Tr[x].lc].sum - Tr[Tr[y].lc].sum;
	if (sum <= delta) return squery(Tr[y].lc, Tr[x].lc, l, mid, sum);
	else return squery(Tr[y].rc, Tr[x].rc, mid + 1, r, sum - delta);
}

int querypre(int l, int r, int tl, int tr)
{
	int tmp = querysum(rt[l - 1], rt[r], 0, n, tr);
	if (!tmp) return 0;
	int rev = squery(rt[l - 1], rt[r], 0, n, tmp);
	return tl <= rev ? rev : 0;
}

void extendS(int x)
{
	int i = lst, c = S[x] - 'a';
	AS[lst = ++ToT].init();
	AS[lst].ri = AS[lst].maxl = x;
	SAM_AS(i, !AS[i].go[c]) AS[i].go[c] = lst;
	if (!i) return (void) (AS[lst].fa = 1);
	int j = AS[i].go[c];
	if (AS[i].maxl + 1 == AS[j].maxl)
		return (void) (AS[lst].fa = j);
	int p; AS[p = ++ToT] = AS[j]; AS[p].ri = 0;
	AS[lst].fa = AS[j].fa = p;
	AS[p].maxl = AS[i].maxl + 1;
	SAM_AS(i, AS[i].go[c] == j) AS[i].go[c] = p;
}

void extendT(int x)
{
	int i = lst, c = T[x] - 'a';
	AT[lst = ++QAQ].init(); AT[lst].maxl = x;
	SAM_AT(i, !AT[i].go[c]) AT[i].go[c] = lst;
	if (!i) return (void) (AT[lst].fa = 1);
	int j = AT[i].go[c];
	if (AT[i].maxl + 1 == AT[j].maxl)
		return (void) (AT[lst].fa = j);
	int p; AT[p = ++QAQ] = AT[j]; AT[p].ri = 0;
	AT[lst].fa = AT[j].fa = p;
	AT[p].maxl = AT[i].maxl + 1;
	SAM_AT(i, AT[i].go[c] == j) AT[i].go[c] = p;
}

void dfs(int u)
{
	a[dfn[u] = ++QwQ] = u; sze[u] = 1;
	Edge(u) dfs(v), sze[u] += sze[v];
}

void calc_right()
{
	int i;
	For (i, 2, ToT) add_edge(AS[i].fa, i);
	dfs(1);
	For (i, 1, ToT) ins(rt[i - 1], rt[i], 0, n, AS[a[i]].ri);
}

int main()
{
	AS[lst = ToT = 1].init();
	int i, l, r;
	scanf("%s", S + 1);
	n = strlen(S + 1);
	For (i, 1, n) extendS(i);
	calc_right();
	q = read();
	while (q--)
	{
		scanf("%s", T + 1); l = read(); r = read();
		AT[lst = QAQ = 1].init();
		m = strlen(T + 1);
		ll res = 0;
		int u = 1, v = 1, len = 0, dln = 0;
		For (i, 1, m)
		{
			int w, c = T[i] - 'a', sp;
			while (v > 1 && !AT[v].go[c])
				v = AT[v].fa, dln = AT[v].maxl;
			if (AT[v].go[c]) v = AT[v].go[c], dln++;
			while (u > 1 && !AS[u].go[c])
				u = AS[u].fa, len = AS[u].maxl;
			while (u > 1)
			{
				int v = AS[u].go[c];
				int minl = AS[AS[v].fa].maxl + 1, maxl = AS[v].maxl;
				sp = querypre(dfn[v], dfn[v] + sze[v] - 1, l, r);
				if (!sp) u = AS[u].fa, len = AS[u].maxl;
				else
				{
					int tlen = Min(sp - l + 1, maxl);
					if (tlen < minl) u = AS[u].fa, len = AS[u].maxl;
					else {len = Min(len, tlen - 1); break;}
				}
			}
			if ((w = AS[u].go[c]) &&
				(sp = querypre(dfn[w], dfn[w] + sze[w] - 1, l, r))
					&& Min(sp - l + 1, AS[w].maxl) > AS[AS[w].fa].maxl)
						u = AS[u].go[c], len++;
			res += i - Max(len, dln);
			extendT(i);
		}
		printf("%lld\n", res);
	}
	return 0;
}