大致题意:
“abracadabra” > “aabracadabr” > “raabracadab” > “braabracada” > “abraabracad” > “dabraabraca” > “adabraabrac” > “cadabraabra” > “acadabraabr” > “racadabraab”。
大致思路:
把第一个字符串复制一份接在自己后面,并将其作为文本串,把第二个字符串作为模式串,做一遍KMP求出模式串在文本串中出现的位置即可。
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int nMax=250005;
const int mMax=2000005;
char text[mMax],pat[nMax];
int lent,lenp,nnext[nMax];
void get_nnext(){
int i,j=-1;
nnext[0]=-1;
for(i=1;i<=lenp;i++){ //pat[j]是ä¸æ˜¯å¯ä»¥ç†è§£ä¸ºiçš„å‰ä¸€ä¸ªå—符的nnext值所指想的å—符
while(j>-1&&pat[j+1]!=pat[i])j=nnext[j];
if(pat[j+1]==pat[i])j++;
nnext[i]=j;
}
}
int KMP(){
int ans=0,i=0,j=-1;
get_nnext();
for(i=0;i<lent;i++){
while(j!=-1&&pat[j+1]!=text[i]){
j=nnext[j];
}
if(pat[j+1]==text[i])j=j+1;
if(j==lenp-1){
// cout<<"fuck "<<i<<endl;
if(i==lenp-1)return 0;
return lent-i-1;//ans++; //找到一个匹é…
}
}
return -1;
}
int main(){
int t;
while(scanf("%d",&lenp)!=EOF){
scanf("%s%s",text,pat);
for(int i=0;i<lenp;i++){
text[i+lenp]=text[i];
}
lent=2*lenp;
text[lent]='\0';
int ans=KMP();
if(ans!=-1){
printf("%d\n",ans);
}
else{
printf("-1\n");
}
}
return 0;
}
分享到:
相关推荐
KMP算法,详细的解释了如何去匹配字符串。做成了实验报告,希望给大家帮助。
int index(const std::string &s, const std::string &p, const int sIndex = 0) { int i = sIndex, j = 0; if (s.length() || p.length() || sIndex ) { return -1; } while (i != s.length() && j != p....
kmp算法内容概况: 本文将介绍一种名为KMP的字符串匹配算法。KMP算法(Knuth-Morris-Pratt算法)是一种高效的字符串匹配算法,由Donald Knuth、Vaughan Pratt和James H. Morris共同发明。KMP算法通过使用一个称为...
D-KMP体系结构-官方样本这是D-KMP架构的官方示例,展示了一个适用于Android和iOS的简单主/详细应用程序。 有关D-KMP体系结构的更多信息,请阅读相关的。D-KMP体系结构的主要功能: 它使用最新的声明性UI工具包:适用...
kmp算法内容概况: 本文将介绍一种名为KMP的字符串匹配算法。KMP算法(Knuth-Morris-Pratt算法)是一种高效的字符串匹配算法,由Donald Knuth、Vaughan Pratt和James H. Morris共同发明。KMP算法通过使用一个称为...
模式匹配,KMP算法,string-match-kmp-master.zip
KMP算法 字符串匹配算法 The KMP algorithm string matching algorithm
KMP报告:元宇宙产品概念,哪一种消费者更有感 12.15-31页.pdf
KMP扩展器 适用于CSV文件的Mario Kart 7的KMP编辑器。
D-KMP架构Daniele Baroncelli建议的D-KMP体系结构的试用示例,位于: ://danielebaroncelli.medium.com/the-future-of-apps-declarative-uis-with-kotlin-multiplatform-d-kmp-part-1 它:声明性UI(Jetpack编写)...
kmp算法
模板-kmp-库 Kotlin多平台库模板。 有一个针对多平台库的基线设置,该库支持除弃用的wasm32之外的所有kotlin。 特征 本机目标分组和共享sourceSet 包装程序库模块,它声明对所有lib模块的依赖关系 通过allprojects...
kmp算法:查找一个字符串是不是另一个字符串的子串
一个封装有KMP模式匹配算法的String类示例,VC++ 2010下编译通过。
算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP
kMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法Java...
KMP算法
void kmp_matcher(sstring s,sstring s1) { int i = 1,j=1; /* Number of characters mached */ int n = s.length; int m = s1.length; int *x = get_next (s1); while(i) { if(j==0 || s.p[i]==s1.p[j])...
KMP algorithm for matching string problem
KMP算法详解KMP算法详解KMP算法详解KMP算法详解KMP算法详解