kmp：831. KMP字符串

831. KMP字符串

•    题目
•    提交记录
•    讨论
•    题解
•    视频讲解

给定一个字符串 SS，以及一个模式串 PP，所有字符串中只包含大小写英文字母以及阿拉伯数字。

模式串 PP 在字符串 SS 中多次作为子串出现。

求出模式串 PP 在字符串 SS 中所有出现的位置的起始下标。

输入格式

第一行输入整数 NN，表示字符串 PP 的长度。

第二行输入字符串 PP。

第三行输入整数 MM，表示字符串 SS 的长度。

第四行输入字符串 SS。

输出格式

共一行，输出所有出现位置的起始下标（下标从 00 开始计数），整数之间用空格隔开。

数据范围

1≤N≤1051≤N≤105
1≤M≤1061≤M≤106

输入样例：

3
aba
5
ababa

输出样例：

0 2

---

 

代码

#include
 
using namespace std;
 
const int N=100010,M=1000010;
 
int n,m;
int ne[N];
char p[N],s[M];
 
int main()
{
    cin>>n>>p+1>>m>>s+1;
    
    for(int i=2,j=0;i<=n;i++)
    {
        while(j&&p[i]!=p[j+1])  j=ne[j];
        if(p[i]==p[j+1])    j++;
        ne[i]=j;
    }
    
    for(int i=1,j=0;i<=m;i++)
    {
        while(j&&s[i]!=p[j+1])  j=ne[j];
        if(s[i]==p[j+1])    j++;
        if(j==n)
        {
            printf("%d ",i-n);
            j=ne[j];
        }
    }
    
    return 0;
}

之前一直是没有理解，后面苦苦思索了很久，总算是理解了，这个算法的思路就是寻找到一个字符串前面部分和后面部分相同的最大的部分，在进行字符串匹配的时候，使用这个算法可以显著的降低时间复杂度，因为我们在匹配之前对比较短的字符串进行了预处理，我们可以知道比较短的字符串的最长的相同的前面部分和后面部分。

然后就是把算法模板记住，我现在一有时间就先把这个代码模板敲一遍，5.58的挑战时间，我还剩下2.56的时候敲完的，用时3分钟左右，我觉得还算比较快，y总说写算法题百分之七八十都是算法模板，这其实还是给我挺多信心的哈哈