洛谷 3375_[模板]KMP字符串匹配_KMP

发布于 2019-05-21  10 次阅读


题目描述

如题,给出两个字符串s1和s2,其中s2为s1的子串,求出s2在s1中所有出现的位置。
为了减少骗分的情况,接下来还要输出子串的前缀数组next。如果你不知道这是什么意思也不要问,去百度搜[kmp算法]学习一下就知道了。
若干行,每行包含一个整数,表示s2在s1中出现的位置
接下来1行,包括length(s2)个整数,表示前缀数组next[i]的值。


思路

随便搞搞注意位置为i-m+2


2017/6/26 增加

#include 
#include 
#include 
using namespace std;
char s1[2000000], s2[20000];
int p[20001];
int len1, len2;
int main()
{
    scanf("%s", s1);
    scanf("%s", s2);
    len1 = strlen(s1);
    len2 = strlen(s2);
    p[0] = -1;
    int j = -1;
    for (int i = 1; i < len2; i++)
    {
        while (s2[j + 1] != s2[i] && j != -1) j = p[j];
        if (s2[j + 1] == s2[i]) j++;
        p[i] = j;
    }
    j = -1;
    for (int i = 0; i < len1; i++)
    {
        while (s1[i] != s2[j + 1] && j != -1) j = p[j];
        if (s1[i] == s2[j + 1]) j++;
        if (j == len2 - 1)
        {
            printf("%d\n", i - j + 1);
            j = p[j];
        }
    }
    for (int i = 0; i < len2; i++)
        printf("%d ", p[i] + 1);
    return 0;
}

原代码

#include 
#include 
#include 
#include 
#define maxn 10000001
using namespace std;
int p[maxn];
char s1[maxn],s2[maxn],fl=0;
int kmp(char a[maxn],char b[maxn])
{
    int n=strlen(a),m=strlen(b);
    int j=-1,ans=0;
    for (int i=0;i
]]>