[Luogu p5829] [template] mismatch tree (string) (KMP)

【 Templates 】 Mismatch tree

Topic link ：luogu P5829

The main idea of the topic

Give you a string , Ask you for the longest public of the two prefixes many times border The length of .
One border A substring is both a prefix and a suffix .

Ideas

in consideration of border Namely fail A chain on the tree .
The public is LCA！
Just get it out .

And then it's important to note that border It can't be yourself , So we have to make a special judgment. If one of the two wants to jump to his father .

Code

#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

const int N = 1e6 + 100;
char s[N];
int n, m, fa[N][21], deg[N];

int LCA(int x, int y) {
    
	if (deg[x] < deg[y]) swap(x, y);
	for (int i = 20; i >= 0; i--)
		if (deg[fa[x][i]] >= deg[y]) x = fa[x][i];
	if (x == y) return x;
	for (int i = 20; i >= 0; i--)
		if (fa[x][i] != fa[y][i]) x = fa[x][i], y = fa[y][i];
	return fa[x][0];
}

int main() {
    
	scanf("%s", s + 1); n = strlen(s + 1);
	for (int i = 2, j = 0; i <= n; i++) {
    
		while (j && s[i] != s[j + 1]) j = fa[j][0];
		if (s[i] == s[j + 1]) j++;
		fa[i][0] = j; for (int k = 1; k <= 20; k++) fa[i][k] = fa[fa[i][k - 1]][k - 1]; deg[i] = deg[fa[i][0]] + 1;
	}
	
	scanf("%d", &m);
	while (m--) {
    
		int x, y;
		scanf("%d %d", &x, &y);
		int ans = LCA(x, y);
		if (ans == x || ans == y) ans = fa[ans][0];
		printf("%d\n", ans);
	}
	
	return 0;
}