字符串匹配算法

字符串匹配是日常开发中经常使用的case，比如在java中就有indexOf方法。我们现在试着来自己实现一下字符串匹配的算法。

1.暴力循环法

暴力算法自然就是双层循环了。具体来说，对于长度为n的源字符串S与长度为m的模式匹配串P，在S中是否存在一个i，当0

interface StringMatcher {

int indexOf(String source, String pattern);
}

class ViolentStringMatcher implements StringMatcher {

    @Override
public int indexOf(String source, String pattern) {
int i = 0, j = 0;
int sLen = source.length(), pLen = pattern.length();
char[] src = source.toCharArray();
char[] pat = pattern.toCharArray();
while(i < sLen && j < pLen) {
if(src[i] == pat[j]) {
                i++;
                j++;
            } else {
// 如果当前字符匹配不成功,则i回溯到此次匹配最开始的位置+1处,也就是i = i - j + 1
// (因为i,j是同步增长的), j = 0;
                i = i - j + 1;
                j = 0;
            }
        }
if(j == pLen) {
return i - j;
        } else {
return -1;
        }
    }

public static void main(String[] args) {
        String source = "abcdefg";
        String pattern = "bc";
        ViolentStringMatcher matcher = new ViolentStringMatcher();
int index = matcher.indexOf(source, pattern);
        System.out.println(index);
    }
}

最后代码的输出结果为：

1

2.KMP算法

在字符串S中寻找P，当匹配到位置i时两个字符串不相等，这时我们需要将字符串f向前移动。常规方法是每次向前移动一位，但是它没有考虑前i-1位已经比较过这个事实，所以效率不高。事实上，如果我们提前计算某些信息，就有可能一次前移多位。KMP算法就是这个思想。
具体KMP算法的讲解请看参考文献，直接上代码。

interface StringMatcher {

int indexOf(String source, String pattern);
}


class KMPMatcher implements StringMatcher {

// 已知next[j] = k,利用递归的思想求出next[j+1]的值
// 如果已知next[j] = k,如何求出next[j+1]呢?具体算法如下:
// 1. 如果p[j] = p[k], 则next[j+1] = next[k] + 1;
// 2. 如果p[j] != p[k], 则令k=next[k],如果此时p[j]==p[k],则next[j+1]=k+1,
// 如果不相等,则继续递归前缀索引,令 k=next[k],继续判断,直至k=-1(即k=next[0])或者p[j]=p[k]为止
private int[] getNext(char[] p) {
int pLen = p.length;
int[] next = new int[pLen];
int k = -1;
int j = 0;
        next[0] = -1;
while(j < pLen - 1) {
if(k == -1 || p[j] == p[k]) {
                k++;
                j++;
                next[j] = k;
            } else {
                k = next[k];
            }
        }
return next;
    }


    @Override
public int indexOf(String source, String pattern) {
int i = 0, j = 0;
char[] src = source.toCharArray();
char[] pat = pattern.toCharArray();
int sLen = src.length;
int pLen = pat.length;
int[] next = getNext(pat);
while (i < sLen && j < pLen) {
// 如果j = -1,或者当前字符匹配成功(src[i] = ptn[j]),都让i++,j++
if (j == -1 || src[i] == pat[j]) {
                i++;
                j++;
            } else {
// 如果j!=-1且当前字符匹配失败,则令i不变,j=next[j],即让pattern模式串右移j-next[j]个单位
                j = next[j];
            }
        }
if (j == pLen)
return i - j;
return -1;
    }

public static void main(String[] args) {
        String source = "abcdefg";
        String pattern = "bc";
        KMPMatcher kmpMatcher = new KMPMatcher();
int result = kmpMatcher.indexOf(source, pattern);
        System.out.println(result);
    }

}

最后的输出结果:

1

参考理解：
1.http://blog.csdn.net/buaa_shang/article/details/9907183
2.http://kenby.iteye.com/blog/1025599
3.https://juejin.im/entry/58edc67461ff4b006925d2e9 很详细的 KMP 算法讲解，逻辑清晰，易懂