mstring.h

字符串的模式匹配(KMP算法)

// Mstring.h: interface for the Mstring class.
//
//////////////////////////////////////////////////////////////////////

#if !defined(AFX_MSTRING_H__507DD002_A4C1_4002_8B96_B05422BE5F00__INCLUDED_)
#define AFX_MSTRING_H__507DD002_A4C1_4002_8B96_B05422BE5F00__INCLUDED_

#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000
#define MAXSTRING 255
#include<iostream>
#include<string>
using namespace std;

class Mstring  
{
private:	
	void get_nextval(string T,int* nextval) {
		i=1;   nextval[1]=0;   j=0;
		while(i<T.length()-1){
			if(j==0 || T[i]==T[j]){
				i++;  j++;
				if(T[i] != T[j])  nextval[i]=j;
				else nextval[i] = nextval[j];
			}
			else j=nextval[j];
		}
	}
public:
	int i,j;
	string S,T;
	int nextval[MAXSTRING];
	Mstring(string tstr){ 
		T=' '+tstr;
		get_nextval(T,nextval);
	}
	virtual ~Mstring();
	void set_sstr(string sstr){ S=' '+sstr; }
	int index_KMP() {
		i=1; j=1;
		while(j<=T.length()-1 && i<=S.length()-1){
			if( j==0 || S[i] == T[j] ) { i++; j++; }
			else j = nextval[j];
		}
		if(j>T.length()-1)  { 
			return i-T.length()+1;
		}
		else return 0;
	}
};

#endif // !defined(AFX_MSTRING_H__507DD002_A4C1_4002_8B96_B05422BE5F00__INCLUDED_)