KMP学习（持续更新）

向右看齐 2023-10-04 11:58 7阅读 0赞

### 文章目录  @\[toc\]  KMP  为什么需要使用KMP  怎么使用KMP  什么是\`next\`数组  为什么要用｀next｀数组  什么是前缀，什么是后缀  KMP模板(c语言)  2、串替换(C++类是实现KMP)  题目描述  输入  输出  样例输入  样例输出 ###

## KMP ##

#### 为什么需要使用KMP ####

> 相对于朴素匹配，我们想要跳过不可能成功的字符串比较，来减少比较的趟数。

#### 怎么使用KMP ####

1.  对于模式串p求出`next`数组
2.  利用`next`数组，将模式串p与主串s作比较

#### 什么是`next`数组 ####

#### 为什么要用｀next｀数组 ####

#### 什么是前缀，什么是后缀 ####

前缀：简单来说，也就是，从第一个字母（必包括）开始往后看到最后一 个字母（不包括）为止的字符串的以第一个字母开头的子串

> （比如“abab”的前缀有a,ab,aba）;

后缀：简单来说，也就是，从最后一个字母（必包括）开始往前看到第一个字母（不包括）为止的字符串的子串

> （比如“abab”的后缀有b,ab,bab）;

最大公共子串长度：也就是前缀和后缀拥有的相同子串的最大长度  
以“abab”为例：

<table> 
 <thead> 
  <tr> 
   <th>模式串的各个子串</th> 
   <th>前缀</th> 
   <th>后缀</th> 
   <th>最大公共元素长度</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>a</td> 
   <td>空</td> 
   <td>空</td> 
   <td>0</td> 
  </tr> 
  <tr> 
   <td>ab</td> 
   <td>a</td> 
   <td>b</td> 
   <td>0</td> 
  </tr> 
  <tr> 
   <td>aba</td> 
   <td>a, ab</td> 
   <td>a, ba</td> 
   <td>1</td> 
  </tr> 
  <tr> 
   <td>abab</td> 
   <td>a, ab, aba</td> 
   <td>b, ab, bab</td> 
   <td>2</td> 
  </tr> 
 </tbody> 
</table>

### KMP模板(c语言) ###

#include<iostream>
    #include<cstdio>
    #include<cstring>
    using namespace std;
    
    const int maxn = 1000005;
    
    char s[maxn];
    char p[maxn];
    int next[maxn];
    int pl , ml;
    
    void getnext()
    {
        next[0] = -1;
        for(int i=0,j=-1;i<pl;)
        {
            if(j==-1||p[i] == p[j]) next[++i] = ++j;
            else j = next[j];
        }
    }
    int Kmp()
    {
        getnext();
        int i=0, j=0;
    	while(i<ml&&j<pl){
    		if(j==-1 || s[i] == p[j]){
    			if(j==pl-1){ //匹配成功
    				return i-pl+1+1; 
    			}
    			i++; j++;
    		}
    		else{
    			j = next[j];
    		}
    	}
        return -1;
    }
    int main()
    {
        scanf("%s",&s);
        scanf("%s",&p);
        ml = strlen(s);
        pl = strlen(p);
    	printf("%d\n",Kmp());
        return 0;
    }

## 2、串替换(C++类是实现KMP) ##

### 题目描述 ###

给出主串、模式串、替换串，用KMP算法找出模式串在主串的位置，然后用替换串的字符替换掉模式串

本题只考虑一处替换的情况，如果你想做的完美一些，能够实现多处替换那可能需要考虑模式串和替换串长度不一致的情况

### 输入 ###

第一个输入t，表示有t个实例

第二行输入第1个实例的主串，第三行输入第1个实例的模式串，第四行输入第1个实例的替换串

以此类推

### 输出 ###

第一行输出第1个实例的主串

第二行输出第1个实例的主串替换后结果，如果没有发生替换就输出主串原来的内容。

以此类推

### 样例输入 ###

4
    aabbccdd
    bb
    ff
    aaabbbccc
    ddd
    eee
    abcdef
    abc
    ccccc
    abcdef
    abc
    c

### 样例输出 ###

aabbccdd
    aaffccdd
    aaabbbccc
    aaabbbccc
    abcdef
    cccccdef
    abcdef
    cdef

#include <iostream>
    #include <string>
    
    using namespace std;
    
    class myString
    {
    private:
    
    	int size;
    	void GetNext(string p,int next[]);
    	int KMPFind(string p,int pos,int next[]);	
    public:
    	string mainstr;
    	myString();
    	~myString();
    	void SetVal(string sp);
    	int KMPFindSubstr(string p,int pos);
    	void tihuan(string p,int pos,int molen);
    };
    
    myString::myString()
    {
    	size = 0;
    	mainstr="";
    }
    
    myString::~myString()
    {
    	size = 0;
    	mainstr="";
    }
    
    void myString::SetVal(string sp)
    {
    	mainstr = "";
        mainstr.assign(sp);
        size  = mainstr.length();
    }
    
    void myString::GetNext(string p,int next[])
    {
    	next[0] = -1;
    	int i = 0,now =-1;
    	while(i<int(p.length()))
    	{
    		if(now==-1||p[i]==p[now])
    		{
    			i++;
    			now++;
    			next[i]=now;
    		}else
    		{
    			now = next[now];
    		}
    	}
    } 
    
    int myString::KMPFind(string p,int pos,int next[])
    {
    	int i=pos,j=0;
    	while(i<size&&j<int(p.length()))
    	{
    		if(j==-1||mainstr[i]==p[j])
    		{
    			i++;
    			j++;
    		}else
    		{
    			j=next[j];
    		}
    	}
    	if(j==int(p.length()))
            return i-j+1;
        else return 0;
    }
    
    int myString::KMPFindSubstr(string p,int pos)
    {
    	int i;
    	int L=p.length();
    	int *next = new int [L];
    	GetNext(p,next);
    //	for(int i=0;i<L;i++)
    //	{
    //		cout<<next[i]<<" ";
    //	 } 
    //	 cout<<endl;
    	 int v=-1;
    	 v = KMPFind(p,0,next);
    	 delete []next;
    	 return v;
    }
    
    void myString::tihuan(string p,int pos,int molen)
    {
    	int len = p.length();
    	string sub1 = mainstr.substr(0,pos);
    	string sub2 = mainstr.substr(pos+molen);
    	mainstr = sub1+p+sub2; 
    }
    
    int main()
    {
    	int t;
    	cin>>t;
    	while(t--)
    	{
    		string mainstr,mostr,tihuanstr;
    		cin>>mainstr>>mostr>>tihuanstr;
    		myString ms;
    		ms.SetVal(mainstr);
    		int molen = mostr.length();
    		int pos = ms.KMPFindSubstr(mostr,0)-1;
    		cout<<ms.mainstr<<endl;
    		if(pos!=-1)
    		{
    			ms.tihuan(tihuanstr,pos,molen);
    		}
    		cout<<ms.mainstr<<endl;
    	}
     }