当前位置:网站首页>[template] KMP string matching
[template] KMP string matching
2022-07-06 11:51:00 【Selvaggia】
KMP String matching next Array method
char* strstr(char*str,char*pattern);// The string is very small O(m.n)
There are small strings that can be matched from end to end in the substring , The pointer doesn't have to go back to the beginning every time .
Before matching , Analyze the pattern string in detail , Make clear next The meaning of value ,
p[0 ~ j]==p[ (i-j) ~i] , From p[0] Start length is len=j+1, There are p[j]=
p[i] So once p[i+1] And t[?] It's not equal ,t[?] The next one is with p[j+1] Compare ,next[i+1]=j+1
for example next[6]=3 , Mode string slave 0-5 In this substring , The head and tail can match
Small string from 0 Start the subscript at the end of this small string Move back a bit
In fact, we can also find , KMPKMP The reason why the algorithm is fast , Not just because of its mismatch handling scheme , More importantly, it takes advantage of the characteristics of prefix and suffix , Never look for again and again , We can see that there is only one loop for matching in the code , in other words KMPKMP The algorithm has a “ Optimal history processing ” The nature of , And this property is also based on KMP The core idea of .
t[?] And p[0] All matching failed ,
-1 It means that this point in the main string cannot succeed , The main string moves back a position
Put the front of the pattern string to the failed position Continue matching
If it's with p [ x ] ( x ! = 0 ) p [x](x!=0) p[x](x!=0) Comparison failed , that t[?] And next[x] matching
This form can successfully obtain the matching position , But there is one flaw ,next The array does not correctly reflect The real length of the small string that matches the beginning and end of the pattern string
There is no defect , Compare according to observation , Find out next【i】 i ∈ ( 0 — — p . s i z e ( ) − 1 ) i∈( 0——p.size()-1 ) i∈(0——p.size()−1) Represents the pattern string before i Characters , namely 0~ i-1 The beginning and end of this paragraph match the length of the small string , But 0~p.size()-1 The beginning and end of the whole pattern string match, but the length of the small string is unknown . Observe getNext() Right in the function next The evaluation of array can find ,next The length of the array is p . s i z e ( ) + 1 p.size()+1 p.size()+1 instead of p . s i z e ( ) p.size() p.size(), That is, being n e x t [ p . s i z e ( ) ] next[p.size()] next[p.size()], Can be said 0~p.size()-1 The whole pattern string matches the length of the small string .
【 Templates 】KMP string matching
【 Templates 】KMP string matching
#include <iostream>
#include <algorithm>
using namespace std;
const int N=1e6+5;
int next[N];
void getNext(string p){
next[0]=-1;
int i=0;
int j=-1;
// In the pattern matching string, in the small string that matches the beginning and end ,i Point to the last character of the tail string
// j Point to the last character of the first string ,
// That is to say p[i+1] The position of pointer backtracking when it does not match j+1 It depends on it j location
int len=p.size();//strlen
while(i<len){
if(j==-1||p[i]==p[j]){
i++;j++;// The first and last strings still match, and then continue to move forward
next[i]=j;// Equivalent to p[i]=p[j] be next[i+1]=j+1
// as for j==-1, That is, the pointer goes back from -1 Start comparing ,p[i+1] It must be from j==0 Start comparing
}
else{
j=next[j];// If p[i]!=p[j], that p[i] Just like next[j] Compare
}
}
}
void kmp(string t,string p){
int lt=t.size();
int lp=p.size();
int i=0;
int j=0;
while(i<lt&&j<lp){
if(j==-1||t[i]==p[j]){
i++;
j++;
}
else j=next[j];// such j It could be -1, Then I thought if To judge j==-1
//j==-1 Mode string slave 0 At the beginning j++,t[i] It is impossible to p[0] matching
if(j==(lp)){
cout<<i-lp+1<<endl;
j=next[j];// Go back to p【0】
}
}
}
int main(){
string t;
string p;
cin>>t>>p;
getNext(p);
kmp(t,p);
for(int i=1;i<=p.size();i++){
//next The array length is p.size()+1,
// after p.size() The first value is the length of the matching string in the pattern string
cout<<next[i]<<" ";
}
return 0;
}
There is another way to write , avoid next Value taking -1 Of
#include<iostream>
#include<cstring>
#define MAXN 1000010
using namespace std;
int next[MAXN];
int la,lb,j;
char a[MAXN],b[MAXN];
int main()
{
cin>>a+1;
cin>>b+1;
la=strlen(a+1);
lb=strlen(b+1);
for (int i=2;i<=lb;i++)
{
while(j&&b[i]!=b[j+1])
j=next[j];
if(b[j+1]==b[i])j++;
next[i]=j;
}
j=0;
for(int i=1;i<=la;i++)
{
while(j>0&&b[j+1]!=a[i])
j=next[j];
if (b[j+1]==a[i])
j++;
if (j==lb) {
cout<<i-lb+1<<endl;j=next[j];}
}
for (int i=1;i<=lb;i++)
cout<<next[i]<<" ";
return 0;
}
边栏推荐
- Face recognition_ recognition
- AcWing 1298. Solution to Cao Chong's pig raising problem
- 误删Path变量解决
- L2-007 family real estate (25 points)
- [CDH] modify the default port 7180 of cloudera manager in cdh/cdp environment
- Password free login of distributed nodes
- L2-006 tree traversal (25 points)
- jS数组+数组方法重构
- [Blue Bridge Cup 2017 preliminary] buns make up
- Machine learning notes week02 convolutional neural network
猜你喜欢
Gallery之图片浏览、组件学习
error C4996: ‘strcpy‘: This function or variable may be unsafe. Consider using strcpy_ s instead
[CDH] cdh5.16 configuring the setting of yarn task centralized allocation does not take effect
FTP file upload file implementation, regularly scan folders to upload files in the specified format to the server, C language to realize FTP file upload details and code case implementation
保姆级出题教程
2019腾讯暑期实习生正式笔试
[yarn] CDP cluster yarn configuration capacity scheduler batch allocation
Mysql的索引实现之B树和B+树
Software I2C based on Hal Library
MTCNN人脸检测
随机推荐
L2-006 tree traversal (25 points)
vs2019 使用向导生成一个MFC应用程序
使用lambda在循环中传参时,参数总为同一个值
Yarn installation and use
Solution to the practice set of ladder race LV1 (all)
[mrctf2020] dolls
2020 WANGDING cup_ Rosefinch formation_ Web_ nmap
互联网协议详解
Vert. x: A simple TCP client and server demo
ImportError: libmysqlclient. so. 20: Cannot open shared object file: no such file or directory solution
MongoDB
第4阶段 Mysql数据库
Hutool中那些常用的工具类和方法
Mall project -- day09 -- order module
Composition des mots (sous - total)
Contiki source code + principle + function + programming + transplantation + drive + network (turn)
XML file explanation: what is XML, XML configuration file, XML data file, XML file parsing tutorial
Vert. x: A simple login access demo (simple use of router)
Software I2C based on Hal Library
Library function -- (continuous update)