KMP模板——【# P3375 【模板】KMP】
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中所有出现的位置。
定义一个字符串sss的 border 为sss的一个非sss本身的子串ttt，满足ttt既是sss的前缀，又是sss的后缀。
对于s2s_2s2，你还需要求出对于其每个前缀s′s's′的最长 bordert′t't′的长度。
输入格式
第一行为一个字符串，即为s1s_1s1。
第二行为一个字符串，即为s2s_2s2。
输出格式
首先输出若干行，每行一个整数，按从小到大的顺序输出s2s_2s2在s1s_1s1中出现的位置。
最后一行输出∣s2∣|s_2|∣s2∣个整数，第iii个整数表示s2s_2s2的长度为iii的前缀的最长 border 长度。
输入输出样例 #1
输入 #1
ABABABC ABA输出 #1
1 3 0 0 1说明/提示
样例 1 解释
。
对于s2s_2s2长度为333的前缀ABA，字符串A既是其后缀也是其前缀，且是最长的，因此最长 border 长度为111。
数据规模与约定
本题采用多测试点捆绑测试，共有 4 个子任务。
- Subtask 0（30 points）：∣s1∣≤15|s_1| \leq 15∣s1∣≤15，∣s2∣≤5|s_2| \leq 5∣s2∣≤5。
- Subtask 1（40 points）：∣s1∣≤104|s_1| \leq 10^4∣s1∣≤104，∣s2∣≤102|s_2| \leq 10^2∣s2∣≤102。
- Subtask 2（30 points）：无特殊约定。
- Subtask 3（0 points）：Hack。
对于全部的测试点，保证1≤∣s1∣,∣s2∣≤1061 \leq |s_1|,|s_2| \leq 10^61≤∣s1∣,∣s2∣≤106，s1,s2s_1, s_2s1,s2中均只含大写英文字母。
KMP的意义
KMP 是高效字符串匹配算法，名称取自三位发明者（Knuth、Morris、Pratt）首字母。
核心优化：将字符串匹配的时间复杂度从暴力法的
O(N∗M) 优化至线性 O(N+M)（N= 主串长度，M= 模式串长度）。
核心原理：
通过预处理模式串生成前缀数组，匹配失败时，利用前缀后缀的最长公共部分，让模式串直接滑动到有效位置，避免主串回溯，复用已有匹配结果，而非从头重新匹配。
代码
#include<bits/stdc++.h>usingnamespacestd;constintN=1e6+5;string s1,s2;intmir[N];//N长字符串最长相等前后缀长度，如abcdabc中abc既是前缀又是后缀，长度是3/* mir本文中就叫镜像长，意思是在该字符串中最长相同的前后缀的长度 这即使字符串长度，也是镜像前缀后首字符位置。如长3，前三(0、1、2)是镜像部分，而3是0开始第4个位置， 0123456789 本串 abcdabcabcdabcd 配串 abcdabcd 本串7位置的a和配串7位置的d不一样,比对失败，abcdabc有一样前后abc，跳到前abc继续比对 abcdabc是7位置，串长7mir[7]=镜像(abcd)长4，也就是j=4，略过abc从第四个位置的d继续比对 配串 abcdabcd还失败，再没相同前后缀，从头比对 本串i=7位置，配串也是j=7下标 配串 abcdabcd，ok了 本串i=7位置，配串是j=0下标 i是本串下标，j是配串下标，也是j长镜像的下一个字符。 */voidmk_mir(string s){//递推配串每个前缀(从首位始)的镜像(前后相等)长for(inti=1,j=0;i<s.size();i++){//i是后缀尾字符，其字符串长i+1，j是前缀的尾字符while(j>0&&s[i]!=s[j])j=mir[j];//如果前后缀尾字符不一样，镜像不成立，回溯找镜像镜像的下一个字符//j位置错，j前的j长前缀的镜像mir[j],得到的是镜像长，也是镜像外第一个字符。如3长，0、1、2、3，3是3长外的字符if(s[i]==s[j])j++;//前后缀的尾字符一样，则镜像长一位mir[i+1]=j;//到i位置前缀(串长i+1)的镜像长j}}voidview(string s){//配串各个前缀的是否有镜像cout<<"镜像长"<<endl;cout<<"下标：\t";for(inti=0;i<s.size();i++)cout<<i<<"\t";cout<<endl;cout<<"字符：\t";for(inti=0;i<s.size();i++)cout<<s[i]<<"\t";cout<<endl;cout<<"像长：\t";for(inti=0;i<s.size();i++)cout<<mir[i+1]<<"\t";cout<<endl;cout<<"前缀：\t";for(inti=0;i<s.size();i++)cout<<s.substr(0,mir[i+1])<<"\t";cout<<endl;cout<<"后缀：\t";for(inti=0;i<s.size();i++)cout<<s.substr(i-mir[i+1]+1,mir[i+1])<<"\t";cout<<endl;}intmain(){//freopen("data.cpp","r",stdin);while(cin>>s1>>s2){mk_mir(s2);//递推计算配串各前缀的镜像长//view(s2);inti=0,j=0;while(i<s1.size()){if(s1[i]==s2[j])i++,j++;if(j==s2.size()){//cout<<"找到了"<<s1.substr(i-j,j)<<endl;cout<<i-j+1<<endl;j=mir[j];}elseif(i<s1.size()&&s1[i]!=s2[j]){//比对失败if(j>0)j=mir[j];//要么推进配串，从后缀跳到前缀位置elsei++;//要么推进主串}}}for(inti=0;i<s2.size();i++)cout<<mir[i+1]<<" ";cout<<endl;return0;}