AcWing | KMP字符串

叁歲伎倆 2022-12-19 06:18 188阅读 0赞

怕什么就要直面什么！我就要现在开始写题解！！！

--------------------

**题目描述**

> 给定一个模式串S，以及一个模板串P，所有字符串中只包含大小写英文字母以及阿拉伯数字。
> 
> 模板串P在模式串S中多次作为子串出现。
> 
> 求出模板串P在模式串S中所有出现的位置的起始下标。

**输入格式**

> 第一行输入整数N，表示字符串P的长度。
> 
> 第二行输入字符串P。
> 
> 第三行输入整数M，表示字符串S的长度。
> 
> 第四行输入字符串S。

**输出格式**

> 共一行，输出所有出现位置的起始下标（下标从0开始计数），整数之间用空格隔开。  
> 数据范围
> 
> 1≤N≤105
> 
> 1≤M≤106

**输入样例：**

3
    aba
    5
    ababa

**输出样例：**

0 2

--------------------

**思路：**

*  经典的kmp算法中最关键的就是求next数组了
 *  next数组的本质就是求相应长度子串的最大前缀后缀相同的值。
 *  得到next数组以后，在重新匹配下一个环节的时候，能减少重新匹配的次数，也就是不用从头开始匹配。
 *  举个例子来理解：

> 被匹配串 S=\[ababcababefd\]  
> 模板串：P=\[ababefd\]

*  当匹配到下标为4的字符时，S\[4\]=‘c’,P\[3+1\]=‘e’，(下标分别从1和0开始)两者不匹配了，最朴素的做法是将P\[0\]对准S\[1\]从头开始匹配对吧？但是显然是不可能匹配成功的，KMP的做法就是让P\[0\]直接跳到S\[2\]开始匹配，才有可能配对成功。
 *  为啥是S\[2\]呢？这个时候其实就是从P的next\[3\]=2的来的 ，再来深化一下next求的是P子串里面前缀后缀相等的最大长度：

<table> 
 <thead> 
  <tr> 
   <th>P的子串</th> 
   <th>最大匹配前缀</th> 
   <th>最大匹配后缀</th> 
   <th>next数组</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>a</td> 
   <td>\</td> 
   <td>\</td> 
   <td>next[0]=0</td> 
  </tr> 
  <tr> 
   <td>ab</td> 
   <td>a</td> 
   <td>b</td> 
   <td>next[1]=0</td> 
  </tr> 
  <tr> 
   <td>aba</td> 
   <td>a</td> 
   <td>a</td> 
   <td>next[2]=1</td> 
  </tr> 
  <tr> 
   <td>abab</td> 
   <td>ab</td> 
   <td>ab</td> 
   <td>nect[3]=2</td> 
  </tr> 
  <tr> 
   <td>ababe</td> 
   <td>\</td> 
   <td>\</td> 
   <td>next[4]=0</td> 
  </tr> 
 </tbody> 
</table>

**时间复杂度分析：**  
算法中有两个循环，且循环中的语句也是最多执行n次，所以是O(2n），省略常数，于是就是O(n)。

**完整代码：**

#include<iostream>
    using namespace std;
    const int N=100010,M=1000010;
    int n,m;
    char p[N],s[M];
    int ne[N];
    int main(){ //总时间为O(n),因为for循环中的while循环最多执行n次
        cin>>n>>p+1>>m>>s+1;
        //求next过程
        //next[1]=0所以不用算，就是如果第一个匹配事变就要从0开始了，这题i是从1开始的
        for(int i=2,j=0;i<=n;i++){ 
            while(j&&p[i]!=p[j+1]) j=ne[j];//不匹配 j退回到ne[j]的位置
            if(p[i]==p[j+1])j++;//如果该位匹配 就继续往后匹配
            ne[i]=j;
        }
    
        //kmp匹配过程
        for(int i=1,j=0;i<=m;i++){ 
            while(j&&s[i]!=p[j+1])j=ne[j];//如果不匹配 j=nextj
            if(s[i]==p[j+1])j++;//该位匹配，j继续往后移
            if(j==n){ //匹配成功
                printf("%d ",i-n);//输出匹配成功的起始位置，因为下标从0开始所以不用+1了
                j=ne[j];//再匹配下一次的时候j最少往后以多少就又能重新开始匹配
            }
        }
        return 0;
    }

--------------------

Reflection：

*  自己表述的时候还是有点模糊，这大概就是写题解的好处吧，帮助理清楚思路，看看自己到底懂没懂。
 *  过几天回来复盘可能能表述得更清晰一些！