KPM字符串匹配next矩阵计算
特别申明，本文转载自：.html
网上看了很多KMP字符串匹配的博客，这篇是讲的最通俗易通的。下面贴出博客的内容，膜拜。
内容贴出来看不了，直接点链接吧，保证能看明白。下面贴出hihocoder #1015 KMP匹配的AC代码
题目链接：=1174439
#include<iostream>
#include<string>
#include<stdio.h>
using namespace std;
void calNext(string str,int Next[])
{int i,k;Next[0]=0;//cout<<Next[0];for(k=0,i=1;i<str.length();i++){while(k>0&&str[k]!=str[i])k=Next[k-1];if(str[k]==str[i]){k++;}Next[i]=k;// cout<<Next[i];}//cout<<endl;
}
int main()
{int num,i,k,flag;string p_str,o_str;freopen("input.txt","r",stdin);cin>>num;while(num--){flag=0;cin>>p_str;cin>>o_str;int *p=new int[p_str.length()];calNext(p_str,p);for(i=0,k=0;i<o_str.length();i++){while(k>0&&o_str[i]!=p_str[k]){k=p[k-1];}if(o_str[i]==p_str[k]){k++;}if(k==p_str.length()){flag++;}}cout<<flag<<endl;delete [] p;}return 0;
}代码大致与转载博客里提供的代码相同，针对题目要求，做了些微修改。KMP还是略显复杂，理解起来有困难。
KPM字符串匹配next矩阵计算
特别申明，本文转载自：.html
网上看了很多KMP字符串匹配的博客，这篇是讲的最通俗易通的。下面贴出博客的内容，膜拜。
内容贴出来看不了，直接点链接吧，保证能看明白。下面贴出hihocoder #1015 KMP匹配的AC代码
题目链接：=1174439
#include<iostream>
#include<string>
#include<stdio.h>
using namespace std;
void calNext(string str,int Next[])
{int i,k;Next[0]=0;//cout<<Next[0];for(k=0,i=1;i<str.length();i++){while(k>0&&str[k]!=str[i])k=Next[k-1];if(str[k]==str[i]){k++;}Next[i]=k;// cout<<Next[i];}//cout<<endl;
}
int main()
{int num,i,k,flag;string p_str,o_str;freopen("input.txt","r",stdin);cin>>num;while(num--){flag=0;cin>>p_str;cin>>o_str;int *p=new int[p_str.length()];calNext(p_str,p);for(i=0,k=0;i<o_str.length();i++){while(k>0&&o_str[i]!=p_str[k]){k=p[k-1];}if(o_str[i]==p_str[k]){k++;}if(k==p_str.length()){flag++;}}cout<<flag<<endl;delete [] p;}return 0;
}代码大致与转载博客里提供的代码相同，针对题目要求，做了些微修改。KMP还是略显复杂，理解起来有困难。
发布评论