#include <iostream>
using namespace std;
int bf(char *a, char *b,int m,int n)//返回值是数组下标
{
int i = 0;//i,j均是数组下标
int j = 0;
while (i<m && j<n)
{
if (a[i] == b[j])//逐个字符进行对比
{
i++;
j++;
}
else
{
i = i - j;//i回溯
i = i + 1;//回溯的位置已经失配了,应该从下一个位置重新开始匹配
j = 0;
}
}
if (j == n)//j超出数组下标范围,即整个temp以完全匹配
{
return i - j;//本轮匹配的开始位置
}
else
return -1;//未匹配
};
int main(){
int m,n;
cout<<"input length of a:";
cin>>m;
cout<<"input length of b:";
cin>>n;
char table[4]={'A','T','C','G'};//设定DNA表
char a[100];//开空间
char b[100];
cout<<"a=";
for (int i = 0; i < m; i++)//利用随机数给产生序列a
{
a[i]=table[rand()%4];
cout<<a[i];
}
cout<<endl<<"b=";
for ( i = 0; i <n; i++)//产生序列b
{
b[i]=table[rand()%4];
cout<<b[i];
}
cout<<endl;
int l = bf(a,b,m,n); //输出第一位
printf("%d", l);
cout<<endl;
return 0;
}