『JZOJ 4669』【NOIP2016提高A组模拟7.19】弄提纲

Problem

link

Solution

KMP处理出$P_i​$（就是所谓的next数组）

我们可以把 $P_i$看成：点$ i$ 的父亲是$P_i$。这样实际上$P$ 数组的存在就构成了一棵树。
然后现在问题变成了给两个点 $x$ 和$ y$，求他们的$\rm lca$ 以及$\rm lca$ 的深度，然后用倍增求$\rm lca$，$\rm rmq$
求$\rm lca$，或$ \rm tarjan $求$\rm lca$等都是可以的。时间复杂度 $O(n)$或 $O(n\ log\ n)$

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring> 
const int MAXN = 1e5 + 10;
using namespace std;
typedef long long ll;

struct poi
{
	int x;
	poi *nt;
} *a[MAXN];
int i, n, len, l, r, s, ans, p[MAXN], dep[MAXN], fa[MAXN][30];
char st[MAXN];

inline void link(const int &x, const int &y)
{
	poi *p = new poi;
	p->x = y;
	p->nt = a[x];
	a[x] = p;
}
inline void dfs(const int &x)
{
	poi *p = new poi;
	for (p = a[x]; p; p = p->nt)
		if (p->x != fa[x][0])
		{
			dep[p->x] = dep[x] + 1;
			fa[p->x][0] = x;
			dfs(p->x);
		}
}
inline void pre()
{
	p[1] = 0;
	len = strlen(st + 1);
	register int j = 0;
	for (register int i = 2; i <= len; ++i)
	{
		while (j && st[i] != st[j + 1]) j = p[j];
		if (st[i] == st[j + 1]) j++;
		p[i] = j;
	}
	for (register int i = 1; i <= len; ++i) link(i, p[i]), link(p[i], i);
	dfs(0);
	for (j = 1; j <= 26; ++j)
		for (register int i = 1; i <= len; ++i)
			fa[i][j] = fa[fa[i][j - 1]][j - 1];
	return;
}
inline int getlca(int x, int y)
{
	if (dep[y] > dep[x]) swap(x, y);
	register int d = dep[x] - dep[y];
	for (register int i = 0; i <= 26; ++i)
		if (d & (1 << i))
			x = fa[x][i];
	if (x == y) return x;
	for (register int i = 26; i >= 0; i--)
		if (fa[x][i] != fa[y][i])
			x = fa[x][i], y = fa[y][i];
	return fa[x][0];
}
inline void _read(int &x)
{
	x = 0;
	char t = getchar();
	while (!isdigit(t)) t = getchar();
	while (isdigit(t))
	{
		x = x * 10 + t - '0';
		t = getchar(); 
	}
}
int main()
{
	gets(st + 1);
	pre();
	_read(n);
	for (register int i = 1; i <= n; ++i)
	{
		_read(l), _read(r);
		register int lca = getlca(l, r);
		printf("%d %d", dep[lca], lca);putchar('\n');
	}
	return 0;
}