模式匹配(子串问题)

客官°小女子只卖身不卖艺 2022-08-04 16:48 63阅读 0赞

B-F算法

就是暴力搜索，易于理解，效率不高

KMP算法

关键就是预处理NEXT数组，利用之前的失败信息减少主串匹配次数。不需要回溯是关键啦~

\#include<iostream>  
\#include<string>  
using namespace std;  
  
  
template<class T>  
class Node  
\{  
private:  
public:  
        typedef struct pNode  
\{  
pNode \*pnext;  
   pNode \*ppre;  
T data;  
\}plist;  
  
plist \*head;  
\#if 1  
Node()\{\}  
   Node(string data,int n)                        //构造函数   
   \{                
  
   this->head = Create\_list(data,n);  
   \}  
\#endif     
~Node()\{\}  
       //输出链表数据   
void output()  
\{  
plist \*p;  
p = this->head;  
while(p != NULL)  
\{  
cout << p->data <<" ";  
p = p->pnext;  
\}  
cout<<endl;  
\}   
  
void replace\_string(string pattern,string list)  
\{  
int j;  
int temp;  
int next\[100\];  
int len\_list;  
int len\_next;  
  
  
plist \*new\_head;  
plist \*list\_head = new plist;  
plist \*temp\_p;  
  
  
//创建替换list链；  
len\_list = list.length();  
list\_head = Create\_list(list,len\_list);  
new\_head = this->head;  
          
memset(next,0,sizeof(next));  
len\_next = cal\_next(next,pattern);     //计算Next数组   
  
j = 0;  
while(new\_head != NULL)  
\{  
//KMP  
if(new\_head->data == pattern\[j\])  
\{  
  
if(j == len\_next - 1)             //找到匹配模式  
\{  
       temp = 0;//替换  
temp\_p = new\_head;  
while(temp != len\_next)//找到要替换的节点的前一节点；  
\{  
temp++;  
temp\_p = temp\_p->ppre;  
\}  
  
  
list\_head = Create\_list(list,len\_list);//创建新的List链  
temp\_p->pnext = list\_head;  
list\_head->ppre = temp\_p;  
  
  
temp\_p = list\_head;  
//找list尾节点  
while (temp\_p->pnext != NULL)  
\{  
temp\_p = temp\_p->pnext;  
  
  
\}  
temp\_p->pnext = new\_head->pnext;   //替换链尾  
if (new\_head->pnext != NULL)  
\{  
new\_head->pnext->ppre = temp\_p;  
\}  
  
//cout<<"========================================="<<endl;  
j = 0;  
new\_head = new\_head->pnext;  
\}  
else  
\{  
j++;  
new\_head = new\_head->pnext;  
\}  
\}  
else  
\{  
if(j == 0 || next\[j - 1\] == -1)  
\{  
j = 0;                          //第一个元素或者无匹配前缀  
new\_head = new\_head->pnext;  
\}  
else  
\{   
j = next\[j - 1\] + 1;//匹配前缀  
\}  
\}  
   
            
  
  
  
\}  
\}  
  
protected:  
//导入串S   
virtual plist \*Create\_list(string s,int count)  
\{   
   int i;  
plist \*phead = new plist;  
plist \*temp;  
  
phead->data = s\[0\];  
temp = phead;  
  
for(i = 1;i < count;i++)  
  
\{  
plist \*p =  new plist;  
p->data = s\[i\];  
temp->pnext = p;  
p->ppre = temp;  
temp = p;   
\}   
  
temp->pnext = NULL;   //链表尾处理   
phead->ppre = NULL;  
return phead;  
  
\}  
int  cal\_next(int \*next,string patt) //建立匹配表   
\{  
int i;  
int j;  
int len;  
  
next\[0\] = -1;  
len = patt.length();  
  
j = 0;  
for(i = 1;i < len;i++)  
\{  
if(patt\[i\] == patt\[j\])  
\{  
next\[i\] = j;  
j++;  
\}  
else   
if(patt\[0\] == patt\[i\])  
   \{  
       next\[i\] = 0;  
j = 1;       
   \}  
else  
\{  
j = 0;  
next\[i\] = -1;  
\}  
\}  
\#if 0  
for(i = 0;i < len;i++)  
\{  
cout<<next\[i\]<<" ";  
   \}  
\#endif  
return len;  
\}  
  
\};  
//\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*   
//子类（有Bug）   
\#if 0  
template<class T>  
class Seqlist:public Node<T>  
\{  
public:  
        typedef struct pNode  
\{  
pNode \*pnext;  
pNode \*ppre;  
T data;  
\}plist;  
  
plist \*head = new plist;  
  
   Seqlist()\{\}  
   Seqlist(string data,int n)  
   \{  
   this->head = this->Create\_list(data,n);  
   //Create\_list(data,n);  
   \}  
\};  
\#endif  
//\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*   
int main()  
\{  
    int len;  
string src = "cabaabcabaabcabaab";  
string str = "abaab";  
string list\_str = "\*\*\*";  
  
len = src.length();  
//Seqlist<char> p(str,len);  
    Node<char> demo(src,len);  
  
demo.output();  
demo.replace\_string(str,list\_str);  
demo.output();  
  
    return 0;  
\}  ![SouthEast][]

[SouthEast]: /images/20220805/0eb2f77732894e79b7ffd8c6887cba38.png