kmp算法实现串匹配
2021/11/27 17:15:30
本文主要是介绍kmp算法实现串匹配,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
#include <iostream> #include <cstring> using namespace std; /* * 因为碱基对配对只有A T G C 四种基本碱基,极其容易出现重复序列,故采用kmp算法 * 来解决问题 */ char t[1000];//文本串 char p[1000];//模式串 int * nextBuild(const char *pattern) { size_t m=strlen(pattern),j=0; int *N=new int[m]; int state=N[0]=-1; while(j<m-1) { if(state<0|| pattern[j] == pattern[state]) { state++,j++; N[j]= pattern[j] == pattern[state] ? N[state] : state; }else { state=N[state]; } } return N; } void overturn(char *pattern) { unsigned int i=0; while(pattern[i]!=0) { switch(pattern[i]) { case 'A': pattern[i]='T'; break; case 'T': pattern[i]='A'; break; case 'G': pattern[i]='C'; break; case 'C': pattern[i]='G'; break; } i++; } } int match(char *text,char *pattern) { int m=int(strlen(text)),i=0; int n=int(strlen(pattern)),j=0; int *next= nextBuild(pattern); while(i<m&&j<n) { if(j<0||text[i]==pattern[j]) { j++,i++; }else j=next[j]; } delete [] next; return i-j+1; } int main() { gets(t); gets(p); overturn(p); int position= match(t,p); if(position<=(strlen(t)-strlen(p)+1)) { printf("%d\n",position); }else cout<<0<<endl; return 0; }
这篇关于kmp算法实现串匹配的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-07-02springboot项目无法注册到nacos-icode9专业技术文章分享
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)