本文主要是介绍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算法实现串匹配的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!