P3375 【模板】KMP字符串匹配

https://www.luogu.org/problemnew/show/P3375

题目描述

如题，给出两个字符串s1和s2，其中s2为s1的子串，求出s2在s1中所有出现的位置。

为了减少骗分的情况，接下来还要输出子串的前缀数组next。

（如果你不知道这是什么意思也不要问，去百度搜[kmp算法]学习一下就知道了。）

输入输出格式

输入格式：

第一行为一个字符串，即为s1

第二行为一个字符串，即为s2

输出格式：

若干行，每行包含一个整数，表示s2在s1中出现的位置

接下来1行，包括length(s2)个整数，表示前缀数组next[i]的值。

输入输出样例

输入样例#1：复制

ABABABC
ABA

输出样例#1：复制

1
3
0 0 1

说明

时空限制：1000ms,128M

数据规模：

设s1长度为N，s2长度为M

对于30%的数据：N<=15，M<=5

对于70%的数据：N<=10000，M<=100

对于100%的数据：N<=1000000，M<=1000000

样例说明：

所以两个匹配位置为1和3，输出1、3

重新开始学习kmp

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define lson l,mid,rt<<1
 4 #define rson mid+1,r,rt<<1|1
 5 #define sqr(x) ((x)*(x))
 6 #define maxn 1000005
 7 typedef long long ll;
 8 typedef unsigned long long ull;
 9 const ull MOD=257;
10 /*#ifndef ONLINE_JUDGE
11         freopen("1.txt","r",stdin);
12 #endif */
13 
14 int Next[maxn];
15 char s1[maxn];
16 char s2[maxn];
17 
18 void getNext(char *s){
19     int j=0;
20     int len=strlen(s+1);
21     for(int i=2;i<=len;i++){
22         while(j&&s[i]!=s[j+1]) j=Next[j];
23         if(s[j+1]==s[i]) j++;
24         Next[i]=j;
25 
26     }
27 }
28 
29 void KMP(){
30     getNext(s2);
31     int j=0;
32     int len1=strlen(s1+1);
33     int len2=strlen(s2+1);
34     for(int i=1;i<=len1;i++){
35         while(j&&s2[j+1]!=s1[i]) j=Next[j];
36         if(s2[j+1]==s1[i]) j++;
37         if(j==len2){
38             cout<<i-len2+1<<endl;
39             j=Next[j];
40         }
41     }
42 }
43 
44 int main(){
45     #ifndef ONLINE_JUDGE
46         freopen("1.txt","r",stdin);
47     #endif
48     //std::ios::sync_with_stdio(false);
49     cin>>(s1+1);
50     cin>>(s2+1);
51     KMP();
52     int len=strlen(s2+1);
53     for(int i=1;i<=len;i++){
54         cout<<Next[i]<<" ";
55     }
56 }

View Code