KMP算法

题目描述
学习KMP算法，给出主串和模式串，求模式串在主串的位置
算法框架如下，仅供参考
输入
第一个输入t，表示有t个实例
第二行输入第1个实例的主串，第三行输入第1个实例的模式串
以此类推
输出
第一行输出第1个实例的模式串的next值
第二行输出第1个实例的匹配位置，位置从1开始计算，如果匹配成功输出位置，匹配失败输出0
以此类推
样例输入
3
qwertyuiop
tyu
aabbccdd
ccc
aaaabababac
abac
样例输出
-1 0 0
5
-1 0 1
0
-1 0 0 1
8

思路

#include<iostream>
using namespace std;
class myString{
	private:
		string mainstr;
		int size;
		void getNext(string p, int next[]){//获取next数组
			int len= p.length();
			int i= 0; 
			next[i]= -1;
			int j= -1;
			while(i< len){
				if(j== -1||p[i]== p[j]){
					i++;j++;
					next[i]= j;
				}
				else
				 j= next[j];
			}
		}
		int KMPfind(string p, int pos, int next[]){
			int i= pos;
			int j= -1;
			int len= mainstr.length();
			int len1= p.length();
			while(i< len&&j< len1){
				if(j== -1||mainstr[i]== p[j]){
					i++; j++;
				}
				else
				  j= next[j];
			}
			if(j>= len1)//j>=len1说明匹配串完全走完了，即有与它匹配的子串
			  return i- len1+ 1;
			else
			  return 0;
		}
	public:
		myString(){
			size= 0;
			mainstr= "";
		}
		void setval(string st){
			mainstr= st;
			size= mainstr.length();
		} 
		int KMP(string p, int pos){
			int len= p.length();
			int *next= new int [len+ 5];
			getNext(p, next);
			
			for(int i= 0; i< len; i++)
			 cout<<next[i]<<' ';
			
			cout<<endl<<KMPfind(p, pos, next)<<endl;
		}
};
int main(){
	int t;
	
	cin>>t;
	while(t--){
		string str;
		string p;
		cin>>str>>p;
		myString mystring;
		mystring.setval(str);
		mystring.KMP(p, 0);
	}
}

最后

以上就是眼睛大饼干为你收集整理的KMP算法的全部内容，希望文章能够帮你解决KMP算法所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。