ICPC字符串：KMP算法训练 题型一：模板题及其变体

例题1：模板题：hudoj 2087 剪花布条

算法分析：

这个题目是一道不允许重叠的单模式、多此出现的KMP算法问题，处理的策略是：
每次匹配成功了之后，就让模式串的下标归零，这样处理的话，就相当于在父串的一个后缀中去做一轮新的KMP算法，从头开始进行模式匹配！

AC代码

#include <iostream>
#include <string>
using namespace std;

string str1, str2;
int nex[1005], ans;
void GetNext(){
	int i = 0, j = -1, len = str2.length();
	nex[0] = -1;
	while(i < len){
		if(-1 == j || str2[i] == str2[j])
			nex[++i] = ++j;
		else
			j = nex[j];
	}
}

int KMP(){
	int i = 0, j = 0, len1 = str1.length(), len2 = str2.length();
	ans = 0;
	GetNext();
	while(i < len1 && j < len2){
		if(-1 == j || str1[i] == str2[j]){
			i++, j++;
			if(len2 == j){
				ans++;
				j = 0;
			}
		}
		else
			j = nex[j];
	}
	return ans;
}
int main(){
	while(cin >> str1 && '#' != str1[0]){
		cin >> str2;
		cout << KMP() << endl;
	}
	return 0;
}

举一反三：

这种问题是不允许重叠的匹配问题，若是允许重叠，该怎么处理呢？
回答：
此时就不能从头开始匹配了，需要修改模式串的回溯：j = nex[j];

练习1：允许重叠的情况

AC代码

#include <iostream>
#include <string>
using namespace std;

const int maxn = 1e6 + 5;
string str1, str2;
int nex[maxn], ans;
void GetNext(){
	int i = 0, j = -1, len = str2.length();
	nex[0] = -1;
	while(i < len){
		if(-1 == j || str2[i] == str2[j])
			nex[++i] = ++j;
		else
			j = nex[j];
	}
}

int KMP(){
	int i = 0, j = 0, len1 = str1.length(), len2 = str2.length();
	GetNext();
	while(i < len1 && j < len2){
		if(str1[i] == str2[j] || -1 == j){
			i++, j++;
			if(len2 == j){
				ans++;
				j = nex[j];
			}
		}
		else
			j = nex[j];
	}
	return ans;
}

int main(){
	cin >> str1 >> str2;
	cout << KMP();
	return 0;
} 

练习2：hduoj 1686 注意输入输出

AC代码

#include <cstdio>
#include <cstring>
using namespace std;

const int maxn = 1e6 + 5;
const int maxm = 1e4 + 5;
char str1[maxn], str2[maxm];
int nex[maxn], ans, t;
void GetNext(){
	int i = 0, j = -1, len = strlen(str2);
	nex[0] = -1;
	while(i < len){
		if(-1 == j || str2[i] == str2[j])
			nex[++i] = ++j;
		else
			j = nex[j];
	}
}

int KMP(){
	int i = 0, j = 0, len1 = strlen(str1), len2 = strlen(str2);
	GetNext();
	ans = 0;
	while(i < len1 && j < len2){
		if(str1[i] == str2[j] || -1 == j){
			i++, j++;
			if(len2 == j){
				ans++;
				j = nex[j];
			}
		}
		else
			j = nex[j];
	}
	return ans;
}

int main(){
	scanf("%d",&t);
	while(t--){
		scanf("%s %s",str2,str1);
		printf("%d\n",KMP());
	}
	return 0;
} 

练习3：hduoj 1711 第一次匹配上的位置

AC代码

#include <cstdio>
#include <cstring>
using namespace std;

const int maxn = 1e6 + 5;
const int maxv = 1e4 + 5;
int a[maxn], b[maxv], nex[maxv], ans, t, n, m;
void GetNext(){
	int i = 0, j = -1;
	nex[0] = -1;
	while(i < m){
		if(-1 == j || b[i] == b[j])
			nex[++i] = ++j;
		else
			j = nex[j];
	}
}

int KMP(){
	int i = 0, j = 0;
	GetNext();
	ans = -1;
	while(i < n && j < m){
		if(-1 == j || a[i] == b[j]){
			i++, j++;
			if(m == j){
				ans = i - m + 1;
				break;
			}
		}
		else
			j = nex[j];
	}
	return ans;
}

int main(){
	scanf("%d",&t);
	while(t--){
		scanf("%d %d",&n,&m);
		for(int i = 0;i < n;i++)
			scanf("%d",&a[i]);
		for(int j = 0;j < m;j++)
			scanf("%d",&b[j]);
		printf("%d\n",KMP());
	}
	return 0;
} 

题型二：Next数组的灵活应用

例题1：前缀匹配 hduoj 3336

AC代码

#include <cstdio>
#include <cstring>

const int maxn = 2e5 + 5;
const int mod = 10007;
char str[maxn];
int nex[maxn], n, ans, t;
void GetNext(){
	int i = 0, j = -1;
	nex[0] = -1;
	while(i < n){
		if(str[i] == str[j] || -1 == j)
			nex[++i] = ++j;
		else
			j = nex[j];
	}
}

int main(){
	scanf("%d",&t);
	while(t--){
		scanf("%d %s",&n,str);
		memset(nex, 0, sizeof(nex));
		GetNext();
		ans = n;
		for(int i = 1;i <= n;i++){
			int temp = nex[i];
			while(temp){
				ans = (ans + 1) % mod;
				temp = nex[temp];
			}
		}
		printf("%d\n",ans);
	}
	return 0;
} 

练习：poj 2752 Seek the Name, Seek the Fame

AC代码

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

const int maxn = 4e5 + 5;
string str;
int nex[maxn], ans[maxn];
void GetNext(){
	int i = 0, j = -1, len = str.length();
	memset(nex, 0, sizeof(nex));
	nex[0] = -1;
	while(i < len){
		if(str[i] == str[j] || -1 == j)
			nex[++i] = ++j;
		else
			j = nex[j];
	} 
}

int main(){
	while(cin >> str){
		GetNext();
		int len = str.length();
		ans[0] = len;
		int i = len, pos = 0;
		while(nex[i] > 0){
			ans[++pos] = nex[i];
			i = nex[i];
		}
		for(int j = pos;j >= 0;j--)
			cout << ans[j] << ' ';
		cout << endl;
	}
	return 0;
}