洛谷P3375 【模板】KMP字符串匹配

题目描述

给出两个字符串 $s1s_1s1 和 s2s_2s2，若 s1s_1s1 的区间 [l,r][l, r][l,r] 子串与 s2s_2s2 完全相同，则称 s2s_2s2 在 s1s_1s1 中出现了，其出现位置为 lll。现在请你求出 s2s_2s2 在 s1s_1s1 中所有出现的位置。$

定义一个字符串 $s2s_2s2，你还需要求出对于其每个前缀 s′s's′ 的最长 border t′t't′ 的长度。$

输入格式

第一行为一个字符串，即为 $s1s_1s1。第二行为一个字符串，即为 s2s_2s2。$

输出格式

首先输出若干行，每行一个整数，按从小到大的顺序输出 $s2s_2s2 在 s1s_1s1 中出现的位置。最后一行输出 ∣s2∣|s_2|∣s2∣ 个整数，第 iii 个整数表示 s2s_2s2 的长度为 iii 的前缀的最长 border 长度。$

输入输出样例

输入 #1

ABABABC
ABA

输出 #1

1
3
0 0 1

说明/提示

样例 1 解释

。

对于 $s2s_2s2 长度为 333 的前缀 ABA，字符串 A 既是其后缀也是其前缀，且是最长的，因此最长 border 长度为 111。$

数据规模与约定

本题采用多测试点捆绑测试，共有 3 个子任务。

Subtask 1（30 points）： $∣s1∣≤15|s_1| leq 15∣s1∣≤15，∣s2∣≤5|s_2| leq 5∣s2∣≤5。$
Subtask 2（40 points）： $∣s1∣≤104|s_1| leq 10^4∣s1∣≤104，∣s2∣≤102|s_2| leq 10^2∣s2∣≤102。$
Subtask 3（30 points）：无特殊约定。

对于全部的测试点，保证 $|s_1|,|s_2| leq 10^61≤∣s1∣,∣s2∣≤106，s1,s2s_1, s_2s1,s2 中均只含大写英文字母。$

思路

比较标准的一个kmp模板题，记录下怎么写kmp匹配字符串

#include<iostream>
#include<stdio.h>
#include<cstring>
using namespace std;

const int maxn = 1000010;
int next1[maxn];
char s1[maxn];
char s2[maxn];
int len1,len2;
int n,k;
void get_next()
{
    int t1=0,t2;//t1后缀 （始终向前 
    next1[0] = t2 = -1;//t2前缀 （一直在变化 
    while(t1<len2)
    {
        if(t2 == -1 || s2[t1] == s2[t2])//abcaby 
        {
            t1++;
            t2++;
            next1[t1] = t2;
        }
        else t2 = next1[t2];//前缀改变 //next[i]数组的i前进一直依靠后缀不后撤式的推动，而前缀的符合情况决定了next[i]中的值 
    }
}
void KMP()
{
    int t1=0,t2=0;
    while(t1<len1)//t1为主字符串游标 t2为子字符串游标 
    {
        if(t2 == -1 || s1[t1] == s2[t2])
            {
                t1++;
                t2++;
            }
        else t2 = next1[t2];
        if(t2 == len2) //遍历完子字符串 
        {
        printf("%d
",t1-len2+1);
        t2 = next1[t2];
        }
    }
}
int main()
{
    scanf("%s",s1);
    scanf("%s",s2);
    len1=strlen(s1);
    len2=strlen(s2);
    get_next();
    KMP();
    for(int i=1;i<=len2;++i) 
        printf("%d ",next1[i]);//输出next数组 
    return 0;
}