实验目的

1.掌握字符串的顺序存储表示方法。
2.掌握字符串模式匹配算法BF算法或KMP算法的实现。

实验内容

问题描述
医学研究者最近发现了某些新病毒，通过对这些病毒的分析，得知它们的DNA序列都是环状的。
现在研究者已收集了大量的病毒DNA和人的DNA数据,想快速检测出这些人是否感染了相应的病毒。为了方便研究，研究者将人的DNA和病毒DNA均表示成由一些字母组成的字符串序列，然后检测某种病毒DNA序列是否在患者的DNA序列中出现过，如果出现过，则此人感染了该病毒，否则没有感染。例如，假设病毒的DNA序列为baa,患者1的DNA序列为aaabbba,则感染;患者2的DNA序列为babbba,则未感染。(注意，人的DNA序列是线性的，而病毒的DNA序列是环状的。)
输入要求
多组数据，每组数据有1行，为序列A和B, A对应病毒的DNA序列，B对应人的DNA序列。A和B都为“0”时输人结束。
输出要求
对于每组数据输出1行，若患者感染了病毒输出“YES"，否则输出“NO"。
输入样例

abbab abbabaab
baa cacdvcabacsd
abc def
0 0

输出样例

YES
YES
NO

实验提示

此实验内容即要求实现主教材的案例4.1,具体实现可参考算法4.5。算法4.5是利用BF算法来实现字符串的模式匹配过程的，效率较低，可以利用KMP算法完成模式匹配以提高算法的效率。读者可以模仿算法4.5,利用KMP算法来完成病毒感染检测的方案。

strlen()函数：求字符串的长度。

实验代码

BF算法(C++)

#include <iostream>
using namespace std;
#define MAXSIZE 255

//BF算法
int Index_BF(char S[], char T[], int pos)//从第0位开始
{//返回模式T在主串S中第pos个字符开始第一次出现的位置；若不存在，则返回0
	int i = pos; int j = 0;
	int lenS = strlen(S);
	int lenT = strlen(T);
	while (i < lenS && j < lenT)
	{
		if (S[i] == T[j])
		{
			i++; j++;
		}
		else
		{
			i = i - j + 1; j = 0;
		}
	}
	if (j >= lenT)
		return i- lenT;
	else
		return -1;
}

int main()
{
	int pos = 0; int result = 0;
	char s[MAXSIZE] = {}, t[MAXSIZE] = {};
	char output[MAXSIZE] = {};
	while (true)
	{
		cin >> s; cin >> t;
		if (s[0] == '0' && t[0] == '0')
		{
			cout << output << endl;
			break;
		}
		result = Index_BF(t, s, pos);
		if (result == -1)
		{
			strcat_s(output, "No\n");//字符串拼接
		}
		else
		{
			strcat_s(output, "Yes\n");//字符串拼接
		}
	}
}

运行截图

KMP算法(C++)

#include <iostream>
using namespace std;
#define MAXSIZE 50
int next1[MAXSIZE];
//报错next不明确是因为和std命名空间冲突了，它作为全局变量不行，所以改成next1
void get_next(char t[])
{
	char t2[MAXSIZE] = { '0' };
	for (int m = 0; m < MAXSIZE - 1; m++)
	{
		t2[m + 1] = t[m];
		if (t[m] == '\0')
			break;
	}
	int i = 1, j = 0;
	next1[1] = 0;
	while (i < strlen(t))
	{
		if (j == 0 || t2[i] == t2[j])
		{
			i++;
			j++;
			next1[i] = j;

		}
		else
		{
			j = next1[j];
		}
	}
}

//KMP算法
int Index_KMP(char S[], char T[], int pos)//从第0位开始
{//返回模式T在主串S中第pos个字符开始第一次出现的位置；若不存在，则返回0
	int i = 1; int j = 1;
	char s2[MAXSIZE] = { '0' };
	char t2[MAXSIZE] = { '0' };
	for (int m = 0; m < MAXSIZE - 1; m++)
	{
		t2[m + 1] = T[m];
		s2[m + 1] = S[m];
		if (T[m] == '\0')
			break;
	}
	int lenS = strlen(S);
	int lenT = strlen(T);
	while (i <= lenS && j <= lenT)
	{
		if (j == 0 || s2[i] == t2[j])
		{
			i++; j++;
		}
		else
		{
			//i = i - j + 1; j = 0;
			j = next1[j];
		}
	}
	if (j > lenT)
		return i - lenT;
	else
		return -1;
}

int main()
{
	int pos = 0; int result = 0;
	char s[MAXSIZE] = {}, t[MAXSIZE] = {};
	char output[MAXSIZE] = {};

	while (true)
	{
		cin >> s; cin >> t;
		if (s[0] == '0' && t[0] == '0')
		{
			cout << output << endl;
			break;
		}
		get_next(t);
		result = Index_KMP(t, s, pos);
		if (result == -1)
		{
			//cout << "No" << endl;
			strcat_s(output, "No\n");
		}
		else
		{
			//cout << "Yes" << endl;
			strcat_s(output, "Yes\n");
		}
	}
}

运行截图

KMP算法(Python)

#KMP算法
def get_next(t1, next):
    i,j=1,0
    next[1]=0
    while i<len(t1):
        if (j==0 or t1[i]==t1[j]):
            i+=1
            j+=1
            next[i]=j
        else:
            j=next[j]
    #next = next[0:len(t1)]
    return next
                

def Index_KMP(S,T):
    i,j=1,1
    while(i<=len(S)-1 and j<=len(T)-1):
        if(j==0 or S[i]==T[j]):
            #print(S[i],T[j])
            i += 1
            j += 1
        else:
            j=next[j]
            #print(next[j])
    if j>=len(T)-1:
        return i-len(T)
    else:
        return -1


next = 50 *[0]
needPrint = ""
while True:
    a,b = map(str,input().split())
    if a=='0' and b=='0':
        print(needPrint)
        break
    a0=list(a)
    b0=list(b)
    a1=['0']
    b1=['0']
    a=a1+a0
    b=b1+b0
    next = get_next(a, next)
    ans = Index_KMP(b,a)
    if ans>=0:
        needPrint += "Yes\n"
    else:
        needPrint += "No\n"

运行截图

实验小结

实际上，严蔚民实验书上，第二个结果应该是Yes，可能是因为病毒是环状的吧。
可是我个人觉得，基于环状的情况下，baa可以等同aab，但要是等同于aba就有点奇怪了。所以我就按传统的BF和KMP算法来实现了。