Gym 100431E Word Cover 题解：KMP上跑dp

题意：

给你一个串，问你他的每个前缀的最小重复单元，其中单元是可以重叠的，最后按顺序输出即可。比如样例中abaabaa的最小重复单元为abaa，所以相应输出为4。

样例：

input ： abaabaababa

output：1 2 3 4 5 3 4 5 3 10 3

kmp过程就不用多说了，现在我们利用next数组的性质来对问题进行求解。

我们首先用一个ans[maxn]数组来记录最后的答案，且我们的字符串下标从0开始，显然，我们ans[i]的最大值为i+1，我们因此也用此值对其进行初始化。

现在我们考虑什么情况下ans[i]可以得到更小的，更小他能达到多小。

其实这个显然可以知道第i位的ans值只能从ans[next[i]]那里获得，这个就可以根据next数组的性质想一想就明白了，若存在更短的，到i的后面的这段就不成立了。

然后我们考虑i和next[i]位置的两种情况：

第一种情况：i - next[i] ≤ next[i]

此时显然就可以利用ans[next[i]]进行更新了，如果可以形成前面这段，那么一定可以形成后面那段。

第二种情况：i - next[i] > next[i]

这种情况就是此题的难点所在了，乍看之下似乎这种情况下只能放弃用ans[next[i]]来更新ans[i]了，其实不然！！！

样例就给我们了很好的反例，因为样例最后一位的答案是3！

我们用dp[k]来记录最后ans是k的最大的下标，我们假设cnt = ans[next[i]],即在next[i]处的答案，然后如图：

一个比较显而易见的是cnt ≤ next[i]是肯定成立的，而此种假设下我们假设i - next[i] ≤ next[i]，现在决定最终成败的就只剩下dp[cnt]的具体位置了！！！

我们证明 i - dp[cnt] ≤ cnt 时的情况必然可以用cnt来更新ans[i]。

此时状况完全如上图所示，此时在dp[cnt]前已经得知必可由长度为cnt的串来产生，而这cnt长得串同时也肯定是从0到next[i]中长度为cnt的后缀。那么根据next数组的性质，这段串与i-cnt ~ i这段是相同的。我们又假设了 i - cnt ≤ dp[cnt] ,因此我们的i-cnt ~ i这段必然可由与形成dp[cnt]长度相同的串来产生，同时这也是其所有可能的最小答案。

最后当next[i] = -1 的时候就没什么说的了，显然上面说的这些都没用了，直接就赋值给 ans[i] = i + 1，再更新一下 dp[ans[i]] = i 就可以了。

在此表达对此神作法的膜拜之情！

本弱渣的代码如下：

#include <iostream>

#include <cstring>

#include <algorithm>

#include <cstdio>

#include <queue>

#include <vector>

#include <algorithm>

using namespace std;

char word[250010];

int next[250010], ans[250010], dp[250010];

int main() {

	freopen("cover.in", "r", stdin);

	freopen("cover.out", "w", stdout);

	scanf("%s", word);

	int len = strlen(word), k = -1;

	next[0] = -1;

	for (int i = 1; i < len; i++) { 				// KMP构造next数组过程

		while (k != -1 && word[i] != word[k + 1]) k = next[k];

		if (word[i] == word[k + 1]) k++;

		next[i] = k;

	}

	for (int i = 0; i < len; i++) {

		ans[i] = i + 1;					//首先赋值最大的可能值i+1

		if (next[i] != -1) {

			int cnt = ans[next[i]];

			if (i - next[i] <= next[i] || i - dp[cnt] <= cnt) {

				ans[i] = cnt;

			}

		}

		dp[ans[i]] = i;					//用ans[i]去更新dp[ans[i]]

	}

	for (int i = 0; i < len - 1; i++) printf("%d ", ans[i]); printf("%d\n", ans[len - 1]);

	return 0;

}

巴特西

Gym 100431E Word Cover 题解：KMP上跑dp

最新文章

热门文章