VEXOBEN

NOI2016 优秀的拆分

Vexoben
Mar 14, 2019
It takes 9 minutes to read this article.

题目链接：NOI2016 优秀的拆分

（刷新以获取数学公式）

题意

如果一个字符串可以被拆分为 的形式，其中 和 是任意非空字符串，则我们称该字符串的这种拆分是优秀的。

例如，对于字符串 ，如果令 ，，我们就找到了这个字符串拆分成 的一种方式。

一个字符串可能没有优秀的拆分，也可能存在不止一种优秀的拆分。比如我们令 ，，也可以用 表示出上述字符串；但是，字符串 就没有优秀的拆分。

现在给出一个长度为 的字符串 ，我们需要求出，在它所有子串的所有拆分方式中，优秀拆分的总个数。这里的子串是指字符串中连续的一段。

以下事项需要注意：

  1. 出现在不同位置的相同子串，我们认为是不同的子串，它们的优秀拆分均会被记入答案。
  2. 在一个拆分中，允许出现 。例如 存在拆分 。
  3. 字符串本身也是它的一个子串。

数据范围 ：

题解

设为以结尾的串数目，为以开头的 串数目，那么答案就是

考虑对每一个长度计算对的贡献。

先枚举一个，将串切成段，除了最后一段外，所有段都要求长度是，假设第段与第段的长度为，第段与第段长度为，那么就有个位置可以放下一个串，其中的长度是。

求串和的：定位到节点和，利用表求出两者在树上的，那么答案就是，其中是一个结点对应最长串的长度。由于预处理表和枚举时的调和级数，总复杂度就是

#pragma GCC optimize("2,Ofast,inline")
#include<bits/stdc++.h>
#define fi first
#define se second
#define R register
#define mp make_pair
#define pb push_back
#define LL long long
#define Ldb long double
#define pii pair<int, int>
using namespace std;
const int N = 1e5 + 10;
const int inf = 0x3f3f3f3f;

struct SAM {
	int tot, rt, las, tim;
	int nod[N], pre[N], len[N], dep[N], st[N][17], ch[N][26];
	int dfn[N << 1], pos[N << 1], Log[N << 1];
	vector<int> son[N];

	void init() {
		tim = 0;
		for (int i = 1; i <= tot; ++i) {
			pre[i] = len[i] = dep[i] = nod[i] = 0;
			memset(st[i], 0, sizeof st[i]);
			memset(ch[i], 0, sizeof ch[i]);
			son[i].clear();
		}
		tot = rt = las = 1;
	}

	int newnode(int l) {
		++tot;
		len[tot] = l;
		return tot;
	}

	void ins(int c, int x) {
		int p = las, np = las = newnode(len[p] + 1);
		nod[x] = np;
		while (!ch[p][c]) ch[p][c] = np, p = pre[p];
		if (!p) pre[np] = rt;
		else {
			int q = ch[p][c], nq;
			if (len[p] + 1 == len[q]) pre[np] = q;
			else {
				nq = newnode(len[p] + 1);
				memcpy(ch[nq], ch[q], sizeof ch[q]);
				pre[nq] = pre[q]; pre[q] = pre[np] = nq;
				while (ch[p][c] == q) ch[p][c] = nq, p = pre[p];
			}
		}
	}

	void dfs(int x) {
		dfn[++tim] = x;
		pos[x] = tim;
		dep[x] = dep[pre[x]] + 1;
		for (int i = 0; i < son[x].size(); ++i) {
			dfs(son[x][i]);
			dfn[++tim] = x;
		}
	}

	int _min(int x, int y) {
		return dep[x] < dep[y] ? x : y;
	}

	void prework() {
		for (int i = 2; i <= tot; ++i) {
			son[pre[i]].push_back(i);
		}
		dfs(rt);
		for (int i = 2; i <= tim; ++i) {
			Log[i] = Log[i >> 1] + 1;
		}
		for (int i = 1; i <= tim; ++i) {
			st[i][0] = dfn[i];
		}
		for (int j = 1; j <= 16; ++j) {
			for (int i = 1; i + (1 << j) - 1 <= tim; ++i) {
				st[i][j] = _min(st[i][j - 1], st[i + (1 << j - 1)][j - 1]);
			}
		}
	}

	int lca(int x, int y) {
		x = pos[x]; y = pos[y];
		if (x > y) swap(x, y);
		int len = Log[y - x + 1];
		return _min(st[x][len], st[y - (1 << len) + 1][len]);
	}

	int lcs(int x, int y, int l, int n) {
		int p = lca(nod[x], nod[y]);
		return min(l, len[p]);
	}
}sam1, sam2;

int n;
int f[N], g[N];
char s[N];

void solve() {
	scanf("%s", s + 1);
	sam1.init();
	sam2.init();
	n = strlen(s + 1);
	for (int i = 1; i <= n; ++i) f[i] = g[i] = 0;
	for (int i = 1; i <= n; ++i) sam1.ins(s[i] - 'a', i);
	for (int i = 1; i <= n; ++i) sam2.ins(s[n - i + 1] - 'a', i);
	sam1.prework();
	sam2.prework();
	for (int len = 1; len <= n; ++len) {
		for (int i = 1; i + len * 2 - 1 <= n; i += len) {
			int j = i + len;
			int lcs = sam1.lcs(i + len - 1, j + len - 1, len, n);
			int lcp = sam2.lcs(n + 1 - (i + len), n + 1 - (j + len), len - 1, n);

			if (lcs + lcp < len) continue;
			++f[i + len * 3 - lcs - 1]; --f[i + lcp + len * 2];
			++g[i + len - lcs]; --g[i + lcp + 1];
		}
	}
	for (int i = 1; i <= n; ++i) {
		f[i] += f[i - 1];
		g[i] += g[i - 1];
	}
	long long ans = 0;
	for (int i = 1; i < n; ++i) {
		ans += 1LL * f[i] * g[i + 1];
	}
	cout << ans << endl;
}

int main() {
	int T;
	cin >> T;
	while (T--) solve();
	return 0;
}