字符串的模式匹配（BF算法，KMP算法）

模式匹配含义：给定两个字符串，在主串s中查找子串T的过程就称为字符串的模式匹配。

BF算法：基本思想就是暴力匹配，将子串的第一个字符与主串的第一个字符进行比较，若相等，则比较第二个字符。若不相等，则与主串的第二个字符进行比较，以此类推，直到匹配到为止。

代码如下：

//返回模式串t在主串中从start开始的第一次匹配位数
    public int indexOf(SeqString t,int start){
        if (this!=null && t!=null && t.length()>0 && this.length()>t.length()){
            int slen,tlen,i=start,j=0;
            slen=this.length();
            tlen=t.length();
            while (i<slen && j<tlen){
                if (this.charAt(i)==t.charAt(j)){
                    i++;
                    j++;
                }
                else{
                    //继续比较下一个字串
                    i=i-j+1;
                    j=0;
                }
            }
            if (j>t.length()){
                //匹配成功，返回子串序号
                return i-tlen;
            }
            else{
                return -1;
            }
        }
        return -1;
    }
           

KMP算法是一种改进的字符串匹配算法，主要实现方式是主串的x指针不回溯，修改y指针的指向，使其移动到有效的位置，从而大大提高了字符串匹配效率。

next指针的作用：当x与y指针指向的字符不同时，让y指针指向next[y]对应的位置即可。

next数组保存的就是已匹配过子串前缀的“最长可匹配前缀子串”和“最长可匹配后缀子串”的最长共有元素的长度。

获取next数组代码

public static int[] getNext(String str){
        int[] next=new int[str.length()];
        next[0]=-1;
        //y为索引，len为最长共有元素的长度
        int y=0,len=-1;
        //定义一个循环，用来计算next数组
        while (y<str.length()-1){
            //处理len何y指向模式串中字符相等的情况
            if (len==-1 || str.charAt(len)==str.charAt(y)){
                y++;
               len++;
               next[y]=len;
            }
            //处理len何y指向模式串中字符不相等的情况
            else{
                len=next[len];
            }
        }
        return next;
    }

           

KMP算法代码

public static int KmpSearch(String str1,String str2){
        int[] next=getNext(str2);
        int x=0,y=0;
        while (x<str1.length()&& y<str2.length()){
            if (y==-1 || str1.charAt(x)==str2.charAt(y)){
                x++;
                y++;
            }
            else{
                y=next[y];
            }
        }
        if (y==str2.length()){
            return x-y;
        }
        return -1;
    }
           

获取next数组优化算法代码

public static int[] getNext(String str){
        int[] next=new int[str.length()];
        next[0]=-1;
        //y为索引，len为最长共有元素的长度
        int y=0,len=-1;
        //定义一个循环，用来计算next数组
        while (y<str.length()-1){
            //处理len何y指向模式串中字符相等的情况
            if (len==-1 || str.charAt(len)==str.charAt(y)){
//                y++;
//                len++;
                //如果len和y指向的字符相等  KMP算法优化
                if(str.charAt(++len)==str.charAt(++y)){
                    next[y]=next[len];
                }
                else{
                    next[y]=len;
                }
                next[y]=len;
            }
            //处理len何y指向模式串中字符不相等的情况
            else{
                len=next[len];
            }
        }
        return next;
    }
           

完整代码如下

//实现KMP算法
    public static int KmpSearch(String str1,String str2){
        int[] next=getNext(str2);
        int x=0,y=0;
        while (x<str1.length()&& y<str2.length()){
            if (y==-1 || str1.charAt(x)==str2.charAt(y)){
                x++;
                y++;
            }
            else{
                y=next[y];
            }
        }
        if (y==str2.length()){
            return x-y;
        }
        return -1;
    }
    //计算next数组
    public static int[] getNext(String str){
        int[] next=new int[str.length()];
        next[0]=-1;
        //y为索引，len为最长共有元素的长度
        int y=0,len=-1;
        //定义一个循环，用来计算next数组
        while (y<str.length()-1){
            //处理len何y指向模式串中字符相等的情况
            if (len==-1 || str.charAt(len)==str.charAt(y)){
//                y++;
//                len++;
                //如果len和y指向的字符相等  KMP算法优化
                if(str.charAt(++len)==str.charAt(++y)){
                    next[y]=next[len];
                }
                else{
                    next[y]=len;
                }
                next[y]=len;
            }
            //处理len何y指向模式串中字符不相等的情况
            else{
                len=next[len];
            }
        }
        return next;
    }