标签：nxt 匹配 cur 后缀 len 算法 字符串 指针

【最小表示法】

最小表示法

循环表示：从一个位置开始向后遍历，到末尾再倒回去最前面。一个字符串（数组）一共有 \(n\) 个。

最小表示法就是最小的循环表示。

例如，3 1 4 9 1 的最小表示法是 1 3 1 4 9.

如果我们用打擂台比大小的方式，因为字符串之间比较需要时间，总共是 \(O(n^2)\) 的，太慢。

---

把字符串列出来，搞两个指针 \(i,j\)，初始 \(i=1,j=i+1\)（字符串视为从 \(1\) 开始）

\(aaaaabcdae\dots\)

两个指针同时往后挪，直到当 \(i,j\) 前进五个位置时，两个指针到各自开始的位置构成两个字符串：\(i\) 代表 \(aaaaa\)，\(j\) 代表 \(aaaab\)。出现了第一个不同的位置：第 \(5\) 个。（如果有一个指针到达末尾，让它转回去接着走）

比较一下这两个字符串，发现 \(i\) 的字符串更小。那么 \(j\) 代表的字符串一定不是最小表示法。我们可以让 \(j+1\)，因为从 \(j\) 开始的字符串一定不是最小表示法了。

但是只有 \(j\) 代表的字符串一定不是最小表示法吗？

不，我们看看 \(i,j\) 字符串。

\(i:aaaaa,i+1:aaaa,i+2:aaa,i+3:aa,i+4:a\)

\(j:aaaab,j+1:aaab,j+2:aab,j+3:ab,j+4:b\)

我们发现，不仅是 \(j\) 一定不优于 \(i\)，一直到 \(j\) 之前的字符串的不同位置，\(j'\) 也一定比 \(i'\) 小。

换言之，这一次我们不仅淘汰了 \(j\)，还淘汰了 \(j\) 之后一直到不同位置的位置。

所以 \(j\) 可以直接加上这个长度，在上面的例子就是跳到 \(j+5\)。

像这样一直从 \(i,j\) 两个指针出发，直到找出更优的那个，然后把不优的那个向后跳。直到有一个指针跳出字符串长度就结束。以此时剩下来的指针为开头的循环表示，就是最小表示法。

---

注意点：

1. 如果两个指针转了一圈都完全相等，随便挑一个作为不优的。

2. 如果 \(i=j\)，随便挑一个 \(+1\)。

3. 可以用取模代替转回去的运算。

【KMP】

以前的笔记

朴素：\(O(nm)\) 枚举主串和模式串匹配。

想法：当匹配失败时，不要一个一个跳，直接跳到合适的位置。

定义 \(nxt[i]\)：模式串长度为 \(i\) 的前缀（\(0\sim i-1\)）的最大的使该长度前后缀相等的长度。（真前缀真后缀）

\(nxt[i]\) 也可以理解为：“若 \(A[j]\) 与 \(B[i]\) 失配，下一次尝试让 \(A[j]\) 与 \(B[nxt[i]]\) 匹配”。

如果不存在真前缀真后缀，或者不存在这个长度使得前后缀相等，令 \(nxt[i]=0\)。

例子：

            j

A: a b a c a b a k

B: a b a c a b a w

            i

此时失配，\(nxt[i]=nxt[7]=3\)，用 B 的第 \(3\) 个字符和 A 匹配。（\(0\) 开始）

            j

A : a b a c a b a k

B:OOOOO a b a c a b a w

             i

这时又失配了，\(nxt[i]=nxt[3]=1\).

            j

A : a b a c a b a k

B:OOOOOO O a b a c a b a w

             i

还是失配，此时 \(nxt[1]\) 不存在真前缀，\(nxt[1]=0\).

            j

A : a b a c a b a k

B:OOOOOOO O a b a c a b a w

             i

还是失配，而 \(nxt[0]\) 无意义，直接让 B 去下一个位置匹配。

            j

A : a b a c a b a k .........

B:OOOOOOOOOO a b a c a b a w

               i

那如何求 \(nxt[]\)？注意 \(nxt[i+1]\) 如果增加，至多增加 \(1\)。

a a b c a a b c d

0 1 2 3 4 5 6 7 8

\(nxt[7]=3\)，推 \(nxt[8]\)。

判断 \(B[7]\) 和 \(B[nxt[7]]\) 是否相等，是则 \(nxt[8]=nxt[7]+1\)，否则判断 \(B[7]\) 和 \(B[nxt[nxt[7]]]\) 是否相等 ....... 直到有一次判断为 "是" 或者判断 \(B[7]\) 和 \(B[0]\) 为不相等。

这里有一个要求：\(nxt[],nxt[nxt[]],\dots\) 可以找出所有相等前后缀。

这其实很好理解，\(nxt[i]\) 可以找出前 \(i\) 个的最大前后缀匹配，而 \(nxt[nxt[i]]\) 找出了前 \(nxt[i]\)个的最大前后缀匹配，因为前 \(nxt[i]\) 和后 \(nxt[i]\) 相等，所以前 \(nxt[nxt[i]]\) 和后 \(nxt[nxt[i]]\) 也相等。所以这么找出来的一定都是前后缀匹配。

又 \(nxt[i]\) 找的是最长的，所以一定能找全。

#include <bits/stdc++.h>
using namespace std;


// 计算得到w的nxt数组，nxt[i]表示w的前i个字符中，最长相同前后缀长度 
vector<int> getNxt(string &w) {
	// nxt[0]无意义，nxt[1]为0，从nxt[2]开始推 
	vector<int> nxt = vector<int>(w.size() + 1, 0);
	for (int i = 1; i < w.size(); i++) { // 利用nxt[i]推nxt[i + 1] 
		// 前cur个字符和 w[i]之前的cur个字符相同 
		int cur = nxt[i]; 
		// 故第cur+1个（w[cur]）若和 w[i]相同，则组成i+1前缀的匹配成功 
		while (cur > 0 && w[cur] != w[i]) //不成功则换更短的cur尝试
			cur = nxt[cur];
		if (w[cur] == w[i])  // 若成功，则设置 nxt[i + 1]的值，若最后也没成功，nxt[i + 1]保持初值0即可 
			nxt[i + 1] = cur + 1;
	}
	return nxt; 
}

// 找到所有位置i，使得a[i]开始是一个w 
void kmp(string &a, string &w) {
	vector<int> nxt = getNxt(w);
	// 匹配a[i]和w[j]，若失败a[i]与w[nxt[j]]继续匹配 
	for (int i = 0, j = 0; i <= a.size(); i++) {
		if (j == w.size()) { // 若试图匹配w[w.size()]，则通过过一位置判断已经成功 
			cout << i - w.size() + 1 << endl; // i为成功的后一个位置，则i - w.size()为起始位置，本题下标从1开始故再+1 
			j = nxt[j]; // 成功后也要移动并试着匹配下一个 
		} 
		if (i == a.size()) // 为在末尾匹配w过一位置，需要考虑a过一位置 
			break;
		while (j > 0 && a[i] != w[j]) // 若 w[j]匹配失败但还有相同前后缀，则跳跃 
			j = nxt[j]; 
		if (a[i] == w[j]) // 若能成功，则下次匹配下一个，否则保持0下次从头匹配 
			j++;
	}
	for (int i = 1; i <= w.size(); i++)
		cout << nxt[i] << " ";
	cout << endl; 
} 

string s1, s2;
int main()
{
	cin >> s1 >> s2;
	kmp(s1, s2);
    return 0;
}

【题目们】

Password

考察对 \(nxt[]\) 数组的理解。

我们先求出 \(s\) 的 \(nxt\) 数组，通过 \(nxt[s.size()],nxt[nxt[s.size()]],\dots\) 找出 \(s\) 的所有相等前后缀。

接下来的问题就是，对于固定的前后缀，如何快速判断中间是否存在一个相等的子串？

用 KMP 就太慢了。

我们可以发现：不如假设枚举的固定前后缀为 \(0\sim len-1,s.size()-len\sim s.size()-1\). 并且有一个中间的相等子串 \(l\sim l+len-1\)。

那 \(nxt[l+len]\) 就应该 \(\geq len\) ！（其实挺显然的）

问题就转化为：一个给定的 \(len\)，如何快速判断 \(nxt[1\sim s.size()-1]\) 有没有 \(\geq len\) 的？

这时，我们再给出一个结论：如果一个字符串的一个 \(nxt[]=k\)，那这个字符串就一定会有一些前缀满足：存在长度 \(1,2,\sim k-1\) 的相等前后缀。

所以我们根本没必要每迭代一次 \(nxt\)（更改 \(s\) 的相等前后缀长度） 就循环整个数组，判断是否存在！

我们只要在求 \(nxt\) 后，求 \(nxt[2\sim s.size() - 1]\)（\(nxt[1]\) 是 \(0\) 不用，\(nxt[s.size()]\) 就是前后缀了，我们要找中间部分）的最大值即可。

// 计算得到w的nxt数组，nxt[i]表示w的前i个字符中，最长相同前后缀长度 
void getNxt(string &w) {
	// nxt[0]无意义，nxt[1]为0，从nxt[2]开始推 
	vector<int> nxt = vector<int>(w.size() + 1, 0);
	for (int i = 1; i < w.size(); i++) { // 利用nxt[i]推nxt[i + 1] 
		// 前cur个字符和 w[i]之前的cur个字符相同 
		int cur = nxt[i]; 
		// 故第cur+1个（w[cur]）若和 w[i]相同，则组成i+1前缀的匹配成功 
		while (cur > 0 && w[cur] != w[i]) //不成功则换更短的cur尝试
			cur = nxt[cur];
		if (w[cur] == w[i])  // 若成功，则设置 nxt[i + 1]的值，若最后也没成功，nxt[i + 1]保持初值0即可 
			nxt[i + 1] = cur + 1;
	} 
	// 先求非结束位置的最长公共前后缀长度k 
	// 这说明有非前后缀的k长度子串匹配前缀，实际上，通过这个子串直接构造出1~k-1长度的匹配 
	int k = 0;
	for (int i = 2; i < w.size(); i++)
		k = max(k, nxt[i]);
	// ans为整个w的 <= k长度的最长公共前后缀长度，用cur枚举所有长度 
	int ans = 0, cur = nxt[w.size()]; 
	while (cur > 0) {
		if (cur <= k) {
			ans = cur;
			break;
		}
		cur = nxt[cur];
	} 
	if (ans == 0)
		cout << "Just a legend" << endl;
	else
		cout << w.substr(0, ans) << endl;
}

如果有 \(nxt[]=k\)，那一定有 \(0\sim k-1\) 长度的相等前后缀。

Radio Transmission

如果枚举前缀，用 KMP，是 \(O(n^2)\) 的。

两个性质：

1. 如果 \(s\) 是一个字符串不停循环，然后截下来一部分得来的，那么 \(n-nxt[n]\) 是 \(s\) 的最小循环周期。（手玩一个长一点的字符串就知道了）

2. 我们可以通过 \(n-nxt[n],n-nxt[nxt[n]],\dots\) 找出所有循环周期。

注：POJ2406（Power strings）也用到相关性质。

\(n-nxt[n]\) 是最小循环周期。

Censoring

还是要 KMP 匹配，但是要处理两端拼接的情况。

KMP 的核心是主串的指针不后退，所以我们希望在匹配（删除）了一个模式串的时候，不要倒回去，直接接着匹配。

这个时候就需要解决一个问题：当我们删除了 \(l\sim l+len-1\) 的模式串后，\(l+len\) 落到了 \(l\) 的位置，我们要知道在 \(l\) 之前匹配了多少个字符，这样才能接着原本 \(l+len\) 的字符匹配下去。

我们在 KMP 时（和匹配/删除字符串同步进行），额外对每个位置记录一个匹配位置：\(c[i]=j\) 表示当主串第 \(i\) 个字符第一次匹配时（在 while (j > 0 && a[i] != w[j]) j = nxt[j]; 之前的 \(j\)，就是 \(i\) 要匹配的 \(j\)），是模式串的第 \(j\) 个位置和它匹配了。

为什么是第一次？因为这样才能在删除之后续上最长的提前匹配好的长度。

总结一下：记录一个第一次匹配位置，这样可以使每次匹配成功删除一个子串后，模式串不从头匹配。

---

代码细节：

我们要用栈存着目前处理过的所有位置，以方便我们在匹配成功后，找到字符串开头的在原本字符串的位置，因为记录的匹配位置 \(c[i]\) 是按照原本字符串的位置记录的。

用栈的原因：这不是直接减去模式串长度就能找到开头的，因为可能我们匹配成功的字符串中间本来被不知道多少个之前删除掉了的模式串隔开，只是在删除之后拼起来的。

而且所有匹配结束后，栈剩下的字符就是要输出的字符串，刚好。

记录失配位置，模式串不从头匹配。

OKR-Periods of Words

把 \(a\) 的末尾去掉 \(a\) 的最小循环节即可。

最小循环节的长度就是 \(nxt[nxt[nxt[\dots nxt[n]]]]]\)，再多一层 \(nxt\) 就变成 \(0\) 了。

不加优化：枚举所有前缀 \(1\sim i\)，令 \(cur=nxt[i]\)，不断迭代直到下一层会变成 \(0\)。然后加上 \(i-cur\)。

优化：其实很简单，类似并查集的路径压缩，搜索的记忆化。如果我们要找 \(nxt[x]\) 最终会迭代到哪里，因为 \(nxt[nxt[x]]\) 一定提前算过了，所以我们可以在 \(nxt[nxt[x]]\) 上记录 \(nxt[nxt[x]]\) 会跳到哪里，在查询 \(nxt[x]\) 会跳到哪里的时候只要调用 \(nxt[nxt[x]]\) 的记录即可。

Om Nom and Necklace

\(s\) 可以是一个字符串循环 \(k\) 次，也可是循环 \(k+1\) 次，也可是循环 \(k\) 次后面带上一点点。

朴素：\(l=n-nxt[n],n-nxt[nxt[n]],\dots\) 不断迭代，看一下哪个 \(l\) 满足 \(k\cdot l\le n\le (k+1)\cdot l\).

优化：枚举每个前缀 \(i\)，令 \(len=i-nxt[i]\)，\(cnt=i/len,res=i\%len\)。那么 \(i=cnt\cdot len+res\)

因为要把 \(i\) 分成 \(k\) 段多，所以我们先分成 \(k\) 段，余下 \(((cnt \% k) * len + res)\)，这个余下的肯定不能比一段更多，所以要求 \(<= cnt / k * len\)。

因此，只要 \(((cnt \% k) * len + res) <= cnt / k * len\)，前缀 \(i\) 的答案就是 1。

动物园

不停迭代，直到 \(nxt[i]\leq \dfrac{len}{2}\).

记录一个 \(c[i]\) 表示 \(nxt[i]\) 不停迭代 \(nxt\)，要迭代几次下次才会变成 \(0\)。（其实就是往后能跳几次不到 \(0\)，包括本身）这个可以在求 \(nxt\) 的时候就利用 \(nxt\) 的递推性质同时求。

但是一步一步枚举 \(nxt[i]\) 太慢了，可以用倍增优化。（带个 \(\log\)）

---

印章

先求出 \(nxt\) 数组。

\(f[i]\) 为前缀 \(i\) 的答案，注意到 \(f[i]=i\) 或 \(f[nxt[i]]\).

（想覆盖 \(i\) 至少先覆盖 \(nxt[i]\)）

什么时候 \(f[i]\) 可以 \(=f[nxt[i]]\)？

首先，如果 \(nxt[i]>=i/2\)，肯定可以，可以用两个 \(nxt[i]\) 拼成 \(i\)；

否则：我们可以保证后 \(nxt[i]\) 个位置可以用 \(f[nxt[i]]\) 覆盖，但是必须保证存在一个位置 \(j\) 使得 \(f[j]=f[nxt[i]],i-nxt[i]\le j\)。

这可以感性理解一下，我们只有在后 \(nxt[i]\) 个字符中找到一个前缀的结尾点，才能保证中间 \(i-nxt[i]-nxt[i]\) 的段并上前面 \(nxt[i]\) 个字符可以被 \(f[nxt[i]]\) 覆盖。

标签：nxt,匹配,cur,后缀,len,算法,字符串,指针
From： https://www.cnblogs.com/FLY-lai/p/18000607