题目描述

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

思路

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

2017/6/26 增加

#include <stdio.h>
#include <string>
#include <cstring>
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 <stdio.h>
#include <iostream>
#include <string>
#include <cstring>
#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<n;i++)
    {
        while (a[i]!=b[j+1]&&j!=-1) j=p[j];
        if (a[i]==b[j+1]) j++;
        if (j==m-1)
        {
            printf("%d\n",i-m+2);
            j=p[j];
        }
    }
    return ans;
}
int main()
{
    scanf("%s%s",s1,s2);
    int len=strlen(s2);
    p[0]=-1;
    int j=-1;
    for (int i=1;i<len;i++)
    {
        while (s2[i]!=s2[j+1]&&j!=-1) j=p[j];
        if (s2[i]==s2[j+1])
            j++;
        p[i]=j;
    }
    kmp(s1,s2);
    for (int i=0;i<len;i++)
        printf("%d ",p[i]+1);
}