KMP算法学习笔记

Scroll Down

基于链表的KMP算法

模式串 pattern

需要匹配的串称为模式串

需求分析

查找首个与pattern匹配的子表

DoubleNode<T> search(DoublyList<T> pattern)

数据结构的声明

public class DoublyList<T> extends Object{
    private DoubleNode<T> head;
    private int size;
}
public class DoubleNode<T>                       //双链表结点类,T指定结点的元素类型
{
    public T data;                               //数据域,存储数据元素
    public DoubleNode<T> prev, next;             //地址域,prev指向前驱结点,next指向后继结点
    //构造结点,data指定元素,prev指向前驱结点,next指向后继结点
    public DoubleNode(T data, DoubleNode<T> prev, DoubleNode<T> next)
    {
        this.data = data;                        
        this.prev = prev;                        
        this.next = next;
    }
}

KMP算法解释

BF算法

BF算法匹配一个模式串时,如果发生不匹配,无论什么情况,模式串和匹配串都会回到一开始。这样的时间复杂度为O(m*n),m为模式串长度,n为匹配串长度。
KMP算法就这样出现了。

KMP算法

KMP算法解决了某些情况下模式串不用回到一开始的情况。
例如:对于模式串

a,b,c,a,b,a

对于匹配串

a,b,c,a,b,c,w,a,b,c,a,b,a

我们可以发现,当双方匹配到第6个字母的时候,发生了不匹配,按照BF算法,匹配串需要回到第二个字母开始,模式串需要回到第一个字母开始,但是我们还能发现,在模式串中,c(位置3)之前的部分和c之后的部分是一样的。
我们就可以不需要回到第一个字母,对于匹配串,c(位置6)的前两个字母[a,b],和模式串c(位置3)的前面两个字母是一样的,那我们就不需要比较前两个字母了。我们就可以直接从第三个字母开始比较,这样一直执行下去,就完成了对于模式串的匹配。

next数组

那我们如何知道如果发生了不匹配的情况,下一次该从哪里开始呢。
我们就需要一个数组来存放这种情况,我们称为next数组。
对于模式串:

a,b,c,a,b,a

我们可以发现在b(位置5)之前是有一个一对a是一样的,对于位置6的a,它的前面有一队[a,b]是一样的,我们就可以认为如果在第5个位置发生不匹配,那么我们回到第二个位置,前面一定是匹配的,对于第6个位置,我们就可以认为回到第3个位置,前面是匹配的。

next数组的构建代码
public static <T> int[] getNext(DoublyList<T> pattern)
    {
        int len=pattern.size();
        int[] next = new int[len];
        DoubleNode<T> i= pattern.head.next;
        if (i.next==null)
            return next;
        DoubleNode<T> j=pattern.head.next.next;
        int jIndex=1;       //链表中难以表示指针指向的元素是第几个
        int iIndex=0;       
        next[0]=0;
        while (i!=null && j!=null)
        {
           if (i.data.equals(j.data))       //第一种情况,匹配,next数组中记录慢指针的位置
           {
               next[jIndex]=++iIndex;
               j=j.next;
               i=i.next;
               jIndex++;
           }
           else if(iIndex-1>=0){    //第二种情况,不匹配,但是快指针不在patten的头位置,之需回溯到匹配过的位置即可
               iIndex = next[iIndex-1];
               i=pattern.head.next;
               for (int k=0;k<iIndex;k++)
                   i=i.next;
           }else {     //第三种情况,不匹配,快指针在pattern的头位置,记录next值为0(pattern的头)
               next[jIndex++]=0;
               j=j.next;
           }
        }
        return next;
    }
匹配算法
public DoubleNode<T> search(DoublyList<T> pattern){
        DoubleNode<T> i = this.head.next;
        DoubleNode<T> j = pattern.head.next;
        DoubleNode<T> temp = i;     //存储匹配串匹配位置的指针
        int index=0;    //记录快指针在pattern中的下标
        int[] next = getNext(pattern);
        while (i!=null && j!=null)
        {
            if (j.data.equals(i.data))  //如果匹配,快指针和慢指针都向前
            {
                index++;
                j=j.next;
                i=i.next;
            }else if(j==pattern.head.next)  //如果不匹配,且不匹配发生在pattern的第一个元素
            {
                temp=temp.next;
                i=i.next;
            }
            else {  //如果不匹配,且不是第一个元素,就需要回溯
                temp=i;
                nIndex=next[index-1];   //因为是双向链表,可以换一种方法回溯
                for (int k=0;k<index-nIndex;k++)
                    j=j.prev;
                index=nIndex;
            }
        }
        return j==null?temp:null;  
    }