模式匹配

模式匹配换成人话说出来叫做子字符串查找。就是给定一个一般很长的长度为 N 的文本，和一个一般比较短的长度为 M 的文本，在长文本中找到和短文本相同的位置的一种匹配算法。这个短文本也叫做模式！

实际生活中经常会有在一个文档中查找字符的需求。比如在利用 IDE 工具查找源代码文件中某个变量或者在笔记软件中查找某个关键词都出现在了哪些位置等。这背后应用到的不就是模式匹配，字符串查找的算法吗？

正式出于这种查找需求，才有了对这个问题的研究和应用。模式匹配有 4 种典型算法，暴力查找、KMP 查找、BM 查找以及 RK 查找。

暴力子字符串查找算法

字符串查找最显而易见的就是暴力破解啦，每一个可能的情况都拉出来溜溜呗。设文本的长度为 N ，模式长度为 M 。暴力破解最坏的情况就是 （N-M+1）M ，实际应用中的绝大部分情况下时间复杂度基本与 N 成正比。

public static int ViolenceSearch(String text,String pattern){
        int N = text.length();int M = pattern.length();
        for(int i = 0;i <= N-M;i++){
            int j;
            for(j = 0;j < M;j++){
                if(text.charAt(i+j) != pattern.charAt(j))
                    break;
            }
            if(j == M)
                return i;//找到匹配
        }
        return N;//未找到匹配
    }

暴力破解还可以采用另一种显式回退的算法来实现，时间复杂度基本等于 N * M

public static int backSearch(String text,String pattern) {
        int i,N = text.length();int j,M = pattern.length();
        for(i = 0,j=0;j < M && i < N;i++) {
            if(text.charAt(i) == pattern.charAt(j)) j++;
            else {i -= j;j=0;}
        }
        if(j == M) return i-M;
        else return N;
    }

KMP 子字符串查找算法

KMP 算法就是由 K、M、P 三个人发明的一种算法啦，实际应用中它并没有比暴力查找高效多少。但它的优势是不需要在输入中回退，这使得 KMP 算法适合在长度不确定的输入流中进行查找！

该算法最核心的部分就是要构造一个部分匹配表,然后按照这个部分匹配表来确定如何与模式字符进行比较。至于如何构造部分匹配表，可参考字符串匹配的KMP算法，这是大神阮一峰的文章。那是怎么想到的这种算法呢？我要是知道，那我就是 K、M、P 三个人的合体了。这再一次验证了自己之前的经验，学习的时候同时多看几个教程，这种方式更容易理解晦涩难懂的内容！

到现在，还是没能完全搞懂。但怎么说呢？实际工作中应该不会有自己写这种代码的时候吧，面试考的可能性也很低。投入产出比不大，下次有时间，再好好把思路整理清楚，把代码写出来吧。离搞懂很近了！