编程之美3.1——字符串移位包含的问题（KMP算法）

问题：

给定两个字符串s1和s2，要求判定s2是否能够被s1做循环移位得到的字符串包含。

解法：

我们在对s1进行循环移位时，保留前面移走的数据，会发现只要将s1复制一份接在后面就能够包含匹配的所有情况。然后只要在s1中查找s2的位置就可以了，我们使用KMP算法在时间O(m+n)内就能够找出这个位置。

KMP算法还是一个比较难理解的算法之一，它的改进在于每当一趟匹配过程中出现字符比较不等时，不需回溯i指针，而是利用已经得到的“部分匹配”的结果将模式串向右“滑动”尽可能远的一段距离后，继续进行比较。

模式串T开头的串被称为前缀子串（下图字符串1...f(k-1)-1表示一个前缀子串），在T中第k个字符左边的子串被称为位置k的左子串（下图字符串k-f(k-1)...k-2表示与该前缀子串相匹配的位置k-1的左子串）。这里我们用动态规划的思路实现这个算法，在形式上与书上的实现方式相差比较大，但效率是一样，并且会更好理解和记忆

阶段：在位置k的所有左子串中，所选出的与前缀子串相匹配的长度最长的左子串的后一个字符的位置为f[k]，k=1,2...n，这个后一个字符的位置很特别，它表示若第k个字符匹配失败，就将模式串向右滑动到第f[k]个字符，并与f[k]字符进行比较。
状态：若第k个字符匹配失败接下去只有一个待匹配的字符f[k]。

决策：决定第k字符匹配失败之后下一个待匹配的字符有多种策略，它依次可能是f[k-1], f[f[k-1]], ... , f...f[k-1]，且这个序列是递减的，我们取第一个满足T[k-1]==T[f...f[k-1]]的那个f...f[k-1]，我们将其命为f*[k-1]，f*[k-1]+1的位置就大概可被称为第k个字符匹配失败后接下去要匹配的字符。但若位置f*[k-1]+1的字符等于第k个字符，那我们知道第k个字符匹配失败，第f*[k-1]+1个字符必然也匹配失败，所以若不相等我们可以直接将第f*[k-1]+1个字符设为第k个字符的下一个待匹配字符，若相等我们将第f*[k-1]+1匹配失败之后的那个字符f[f*[k-1]+1]作为第k个字符的下一个待匹配字符。

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

#define MAXN 10001
char S[MAXN];
char T[MAXN];

// 动态规划的KMP算法
int nxt[MAXN];
void state_transfer(char *T, int n, int *next)
{
	int k, u;
	// next[k]表示k的左子串与前缀子串相匹配的字符数
	next[1] = 0;	// 若第一个字符都不匹配，则移位
	for (k=2; k<=n; k++)	// 阶段k,只有一个状态next[k]
	{
		// 决策u表示k-1的左子串与前缀子串相匹配的字符数
		// 找到长度为u的前缀子串使得其最后一个字符等于第k-1字符
		for (u=next[k-1]; u>=1; u=next[u])
			if (T[k-1] == next[u]) break;
		// 若第k字符等于所找到的前缀子串的下一个字符
		// 则若第k字符匹配失败,则第u+1字符肯定也失败,
		// 所以不必尝试匹配第u+1字符,直接匹配next[u+1]字符
		if (T[k] != T[u+1])
			next[k] = u+1;
		else
			next[k] = next[u+1];
	}
}

// 从目标串S中找出模式串T
int findTfromS(char *S, int n, char *T, int *next, int m)
{
	int i, j;
	i=j=1;
	while (i<=n && j<=m)
	{
		// 若S的第i字符匹配T的第j字符,则接着匹配下一字符
		// 否则进而比较T的第next[j]字符
		if (j==0 || S[i]==T[j]) {i++; j++;}
		else j = next[j];
	}
	return i-m;
}


int main()
{
	S[0] = T[0] = "0";
	scanf("%s", S+1);
	strcpy(T, S);
	strcpy(S+strlen(S), T+1);
	scanf("%s", T+1);
	state_transfer(T, strlen(T)-1, nxt);
	int pos = findTfromS(S, strlen(S)-1, T, nxt, strlen(T)-1);
	if (pos == strlen(S))
		printf("false
");
	else
		printf("true: %d
",pos);
}

阅读更多