基于kmp字符串模式配算法的病毒感染检测问题
本⽂记录了数据结构习题解析与实验指导（李冬梅）的实验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 = peat(2);
for(int i =0; i < son.length()- len;++i){
String newSon = son.substring(i, i + len);
test.setSon(newSon);
Position()!=-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];
generated
}
}else{
i = nextval[i];
}
}
}
这就是全部的内容。如果有错误，可以在底下评论，或者私聊我 ，我会及时进⾏修改的。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。