字符串的匹配

串的模式匹配也称为子串的定位操作,即查找子串在主串中出现的位置。它是一个经常用到的算法,也是数据结构中的难点之一。

前提:

设有主串S和子串T,如果在主串S中找到一个与子串T相等的串,则返回串T的第一个字符串在串S的位置。通常:主串S又称目标串,子串T又称模式串。

暴力解法(Brute-Force)

Brute-Force也称朴素模式匹配算法,它的思路很简单。

1、设两个变量分别i、j,i指向主串上的元素,j指向模式串的元素,pose代表这次是从主串的那个位置开始的,最终要返回的是pose。

2、通过判断S[i] == T[j],如果相等话,i++;j++;反之,第三步。直到把模式串匹配完。

3、如果S[I] != T[J],则j = 0;i = ++pose;然后重新执行第二步。

代码实现:

所有代码在我的GitHub仓库中。

这个算法的时间复杂度为O(mn)m、n分别是主串和模式串的数组长度。

KMP算法

总所周知,暴力解法往往都是不够巧妙的。那么就有了KMP算法,它的时间复杂度是O(m+n)。

kmp的算法思想是:

每一趟匹配过程中出现字符不等时,不需要回退主串的指针,而是利用已经得到的前面“部分匹配”的结果,将模式串向左滑动若干个字符之后,继续与主串中的当前字符进行比较。

kmp算法的步骤

1、求next数组,什么是next数组?正如kmp算法那思想所说,将模式串向右滑动若干个字符,那么怎么知道需要滑动多少个字符呢?那就要靠next数组。在模式匹配过程中,若出现字符匹配不相等的情况,即当S[I] != T[j]时(0 <= i < m,0 <= j < n)时,有:S[i-J]S[i-J+1]·····S[i-1] == T[0]T[1]······T[j]至少说明在字符S[i]前还是有一部分字符是相等的。如果模式串中存在首位重叠的真子串即:T[0]T[1]······T[k-1] == T[j-k]T[j-k+1]······T[j-1];然后我们就可以得出来–> S[i-k]S[i-k+1]······S[i-1] == T[0]T[1]······T[k-1],所以我们下一次开始的时候,就从模式串的第k个元素开始就可以了,这样大大减少了算法的时间复杂度。

下面就来确定模式串需要滑动的具体位置。令next[j] = k,则next[j] 表示当模式串中的第j个元素与主串中的对应字符不相等时,需要重现与主串比较的模式串字符位置,也就是需要将模式串滑动到第几个字符与主串比较,求模式串中next的定义如下:

j = 0 next[j] = -1

next[j+1]需要考虑下面两种情况

(1)、若T[j] == T[k] 时,则表示模式串T中满足以下关系:

T[0]T[1]······T[k-1]T[K] == T[j-k]T[j-k+1]······T[j-1]T[j]

则next[j+1] = ++k;

(2)、如果T[j] != T[k] ,则表示T[0]T[1]······T[k-1]T[K] != T[j-k]T[j-k+1]······T[j-1]T[j]

但是已经有T[0]T[1]······T[k-1] != T[j-k]T[j-k+1]······T[j-1],则有k = next[k];

如果此时T[j] == T[k],则T[j+1] = ++k;

如果还是不满足T[j] != T[k]的话,继续回退,k = next[k] ,继续比较,知道next[k] = 0;即k = -1时,next[j+1] = ++k;

下面是我写的求next数组的代码

//    求next数组
    private static int[] getNext(String ps){
        int pLength = ps.length();
        int[] next = new int[pLength];
        char[] p =  ps.toCharArray();
        next[0] = -1;//这是规定
        if (ps.length() == 1) return next;
        next[1] = 0;
        int j = 1;
        int k = next[j];//看看位置j的最长匹配前缀在哪里
//因为这是j-1的时候推j的位置。
        while (j < pLength -1 ){
//            先要推出next[j+1],检查j和k位置上的关系即可
            if ( k == -1 || p[j] == p[k]){
//                next[++j] = next[j] + 1;这个写法不对是因为前面j已经加了,默认就是零了。
                next[j+1] = ++k ;
                j++;
            }else {
                k = next[k];
            }
        }
        return next;
    }

2、我们已经求到了next数组,接下来就是和主串进行匹配,设两个指针,i指向主串上,j指向模式串。如果S[i] == T[j],则i++;j++;如果S[i] != T[j] ,则j = next[j],然后继续进行匹配。最后返回的是i-j。就是开始匹配的第一个元素。



算法      算法

本博客所有文章除特别声明外,均采用 CC BY-SA 3.0协议 。转载请注明出处!