你是人间的四月天

字符串匹配算法

最近在刷leetcode时,运用到了字符串匹配算法.关于字符串匹配算法,之前在查资料时,也做过一些研究,脑海中大概有两种想法:

  • 暴力搜索法

  • KMP算法

下面对这两种算法做一下总结: 首先总结简单易懂,并且利用率较高的暴力搜索法吧!

先明确两个概念:

  • String txt: 被查找的文本,需要从中来查找要求的字符串

  • String pat (pattern): 目标字符串,不少资料中称之为模式

算法的目的是: 在文本字符串txt中查找模式字符串pat第一次出现的位置.

  • 算法思想:

    • 使用指针i跟踪文本

    • 使用指针j跟踪模式

    • 对于每个i,代码首先将j重置为0并不断将它增大,直到找到了一个不匹配的字符或者j==pat.length为止

    • 如果在模式字符串结束之前文本字符串就已经结束(即i==txt.length-pat.length+1思考这个细节,我在第一次写的时候,直接匹配到了txt的最后一个字符.而这样来写则考虑到了txt剩余字符串的长度,减少了不必要的计算次数),那么就没有找到匹配,模式字符串在文本中不存在.约定不存在时返回 txt的长度.

算法代码:

    public static int search(String pat, String txt) {



        int M = pat.length();

        int N = txt.length();

        for (int i = 0; i <= N - M; i++) {

            int j;

            for (j = 0; j < M; j++) {

                if (txt.charAt(i + j) != pat.charAt(j)) {

                    break;

                }

            }

            if (j == M) {

                return i;

            }

        }

        return N;

    }

在典型的字符串处理应用程序中,索引j增长的机会很少,因此该算法的运行时间与N成正比.

暴力搜索算法的另一种具有指导意义的实现:(显式回退)

  • 算法思想

    • 指针i跟踪文本

    • 指针j跟踪模式.

    • 在i和j指向的字符匹配时,代码进行的字符比较和上一个实现相同. 注意,这段代码中的i值相当于上一段代码中的i+j:它指向的是文本中已经匹配过的字符序列的末端(i以前指向的是这个序列的开头)

    • 如果i和j指向的字符不匹配了,那么需要回退这两个指针的值:

    • 将j重新指向模式的开头

    • 将i 指向本次匹配的开始位置的下一个字符

    public static int search2(String pat, String txt) {



        int j, M = pat.length();

        int i, N = txt.length();

        for (i = 0, j = 0; i < N && j < M; i++) {

            if (txt.charAt(i) == pat.charAt(j)) {

                j++;



            } else {

                i -= j;

                j = 0;

            }

        }

        if (j == M) {

            return i - M;

        } else {

            return N;

        }

    }