基于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的数组。两种方法很相似,这里介绍的是第一种方法。)

java
    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代码主体部分

java
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 全部代码

java
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数组的值。

具体代码如下:

java
    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];
            }
        }
    }

这就是全部的内容。如果有错误,可以在底下评论,或者私聊我😉,我会及时进行修改的。


文章作者: vrerain
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 vrerain !
评论
表情 | 预览
Powered By Valine
v1.3.10