本文共 1292 字，大约阅读时间需要 4 分钟。

串(Sequence)

串就是开发中非常熟悉的字符串，是由若干个字符组成的有限序列。

串匹配算法

本节主要研究串的匹配问题，比如：

查找一个模式串(pattern)在文本串(text)中的位置

几个经典的串匹配算法

• 暴力算法
• KMP算法

1.暴力算法

给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回 -1。

示例 1:

输入: haystack = “hello”, needle = “ll”

输入: haystack = “aaaaa”, needle = “bba”

class Solution {
       public int strStr(String haystack, String needle) {
           char[] s1 = haystack.toCharArray();        char[] s2 = needle.toCharArray();        int len1 = s1.length;        int len2 = s2.length;        if(len2==0&&len1==0){
               return 0;        }        // 选定其开始        int i,j;        for(i=0;i<=len1-len2;i++){
               for(j=0;j

2.KMP算法

KMP 算法（Knuth-Morris-Pratt 算法）是一个著名的字符串匹配算法，效率很高，但是确实有点复杂。

先在开头约定，本文用 pat 表示模式串，长度为 M，txt 表示文本串，长度为 N。KMP 算法是在 txt 中查找子串 pat，如果存在，返回这个子串的起始索引，否则返回 -1。

KMP 算法应该是，一波诡异的操作处理 pat 后形成一个一维的数组 next，然后根据这个数组经过又一波复杂操作去匹配 txt。时间复杂度 O(N)，空间复杂度 O(M)。其实它这个 next 数组就相当于 dp 数组，其中元素的含义跟 pat 的前缀和后缀有关，判定规则比较复杂，不好理解。本文则用一个二维的 dp 数组（但空间复杂度还是 O(M)），重新定义其中元素的含义，使得代码长度大大减少，可解释性大大提高。

class Solution {
       public int strStr(String haystack, String needle) {
           int len1 = haystack.length();        int len2 = needle.length();        if(len1==0&&len2==0){
               return 0;        }        if(len1

转载地址：http://ncwdf.baihongyu.com/