C++实现KMP模式匹配算法-白红宇

C++实现KMP模式匹配算法

阅读量：6116 次

发布时间：2019-06-21

本文共 1347 字，大约阅读时间需要 4 分钟。

#include
     
      #include
      
       #include
       
        using namespace std; void Next(const string & pat,vector
        
          & next){	next.resize(pat.length());	if(pat.length() == 0) 		return;	next[0] = -1;		for(size_t pos = 1; pos < pat.length(); ++pos)	{		size_t sublen = pos-1;		while(sublen >= 0)		{				if(pat.substr(0, sublen) == pat.substr(pos-sublen+1, sublen))				break;			--sublen;		}			next[pos] = sublen;	}	return;}int main(void){	string str1, str2;	while(cin >> str1 >> str2) {		vector
         
           next;		Next(str2, next);		vector
          
            pos; int i = 0, j1 = 0, j2 = 0; while(j1 < str1.length()) { j2 = j1 - i; if(j2 >= str2.length()) { // found pos.push_back(i); // move on; int delta = str2.length(); i = i + delta; j1 = max(i,j1); } else if(str1[j1] == str2[j2]) { ++j1; } else { // str1[j1] != str2[j2]; int delta = j2 - next[j2]; i = i + delta; j1 = max(i,j1); } } //output. cout << "str1.length(): " << str1.length() << endl; cout << "str2.length(): " << str2.length() << endl; cout << "str1 from pos: " << endl; for(int i = 0; i < pos.size(); ++i) cout << "[" << (i+1) << "]: " << str1.substr(pos[i], string::npos) << endl; cout << "str2: " << str2 << endl; } return 0;}