本文记录了数据结构习题解析与实验指导（李冬梅）的实验4。
以下是实验内容
1 问题描述
医学研究者最近发现了某些新病毒,通过对这些病毒的分析,得知它们的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”时输入结束。
输入样例
abbab abbabaab
baa cacdvcabacsd
abc def
0 0
输出样例
YES
YES
NO
2 基本思想
因为是环状的，所以可以将字符串A复制一遍。然后每次取原A长度的子串。之后进行字符串匹配，这里的子串匹配算法，我所知道的有两种，一种是BF(简单，但是效率很低),另一种是KMP算法(较难理解，但效率高)。本文是利用KMP算法进行求解。
3 KMP算法
具体的思想就不讲了，讲一讲代码。
首先是求next数组的代码，（这里我的next数组是从下标0开始，第一个元素为-1的数组，另一种方法是从下标1开始存储，第一个元素为0的数组。两种方法很相似，这里介绍的是第一种方法。）
private int[] next;
private String parent;
private String son;
public Kmp(String parent, String son) {
this.parent = parent;
this.son = son;
next = new int[son.length()];
}
public void getNext() {
int len = son.length();
int i = -1;
int j = 0;
next[0] = -1;
while (j < len - 1) {
if (i == -1 || son.charAt(i) == son.charAt(j)) {
i++;
j++;
next[j] = i;
} else {
i = next[i];
}
}
}基本的数据结构就不讲了，讲一讲，关键的while循环。
首先有两个下标i,j分别表示最长前缀的末尾+1和最长后缀的末尾+1.如果相等，则各自加一，这应该很好懂。放一张图解释。
(k就相当于代码中的i,j相当于代码中的j)，首先看第一行红色的。如果k和j位置的元素相等，自然而然地+1，然后看下一元素是否相等。
那么如果不等怎么办呢。这时看图的第二行，首先我们可以证明黄色的部分都是相同的。那么很明显只要让k=next[k]就可以再比较了。如果相等，接着各自加1.不过这里可能你会有个疑问，为啥k要跳到next[k]，才是最长的前缀呢。这里我们就要了解下next[k]的含义next[k]的含义是，k位置前的字符串最大前缀的末尾的下一个。仔细看一下图，你可能就会略懂了。而第三行蓝色的则是next[k]位置的元素和j位置的元素还不相等，那么k = next[next[k]]
的了。
最极端的时候，如果k=next[k] = -1时怎么办，那么就要再if的判断条件加上一句，关于k==-1时的判断。也就是各自都加一，也就是next[j+1]=0,然后k跳到0位置在比较。（当然这条判断也解决了初始时k==-1的问题）
最后可能会对小于len-1产生疑问。为啥不是len呢。因为我们比较的是j,但是我们实际填的是next[j+1].这里如果不懂就需要看一下手推next数组的教程了（注意这里用的是首位是-1的next数组求解方法)。
这里推荐一个视频，我觉得这个视频很好。看过之后有种恍然大悟的感觉😀。视频传送门
4 Kmp代码主体部分
public int getPosition() {
int i = 0;
int j = 0;
while (i < parent.length() && j < son.length()) {
if (j == -1 || son.charAt(j) == parent.charAt(i)) {
i++;
j++;
} else {
j = next[j];
}
}
if (j == son.length()) {
return i - j;
} else {
return -1;
}
}非常简单，就不讲了。
5 全部代码
class Kmp {
private int[] next;
private String parent;
private String son;
public Kmp(String parent, String son) {
this.parent = parent;
this.son = son;
next = new int[son.length()];
}
public void getNext() {
int len = son.length();
int i = -1;
int j = 0;
next[0] = -1;
while (j < len - 1) {
if (i == -1 || son.charAt(i) == son.charAt(j)) {
i++;
j++;
next[j] = i;
} else {
i = next[i];
}
}
}
public void setSon(String son) {
this.son = son;
}
public int getPosition() {
int i = 0;
int j = 0;
while (i < parent.length() && j < son.length()) {
if (j == -1 || son.charAt(j) == parent.charAt(i)) {
i++;
j++;
} else {
j = next[j];
}
}
if (j == son.length()) {
return i - j;
} else {
return -1;
}
}
}
public class Test14 {
public static void main(String[] args) {
// TODO Auto-generated method stub
int flag = 0;
String parent = "cacdvcabacsd";
String son = "baa";
int len = son.length();
Kmp test = new Kmp(parent, son);
son = son.repeat(2);
for (int i = 0; i < son.length() - len; ++i) {
String newSon = son.substring(i, i + len);
test.setSon(newSon);
test.getNext();
if (test.getPosition() != -1) {
System.out.println("YES");
flag = 1;
break;
}
}
if (flag == 0) {
System.out.println("NO");
}
}
}6 nextval数组
我们先来看这种情况，主串为”aaaaaxbcd”,字串为”aaaaab”,我们发现进行b的确认时，b与x不等，然后我们就要跳到倒数第一个a,倒数第二个a………这些过程似乎有些多余，所以我们发现如果后面的4个a,与首位的a相同的话，就完全可以用next[0]的值替代后面的四个a所对应位置的next数组的值。
具体代码如下：
public void getNextval() {
int len = son.length();
int i = -1;
int j = 0;
nextval[0] = -1;
while (j < len - 1) {
if (i == -1 || son.charAt(i) == son.charAt(j)) {
i++;
j++;
if (son.charAt(i) != son.charAt(j)) {
nextval[j] = i;
} else {
nextval[j] = nextval[i];
}
} else {
i = nextval[i];
}
}
}这就是全部的内容。如果有错误，可以在底下评论，或者私聊我😉，我会及时进行修改的。
