menu 首页 标签 归档 视频 关于
字符匹配_KMP算法

一言加载中...

什么是KMP算法

通俗的讲:从一个字符串中找到包含第二个字符串的开始位置。如果存在返回索引位置,否则返回-1。

问题介绍:

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

示例:

//下面解题思路以此为例
输入: haystack = "abacaabacabac", needle = "abacab"
输出:5

输入: haystack = "aaaaa", needle = "bba"
输出: -1

来源:力扣(LeetCode))

KMP算法思路

先看个动态图

首先制作一个前缀表(PrefixTable)

前缀表的构建对于KMP算法很重要,后面会说到作用,以及如何生成。

needle 字符串的前缀表如下:

子串排列 最大公共子串 最大公共子串数
a 0
ab 0
aba a 1
abac 0
abaca a 1
abacab ab 2
索引(i) 0 1 2 3 4 5
字符 a b a c a b
prefix[i] 0 0 1 0 1 2

将Prefix表所有数值后移一位,第一个值补为-1,如下:

索引(i) 0 1 2 3 4 5
字符 a b a c a b
prefix[i] -1 0 0 1 0 1

KMP匹配思想:

  1. 开始匹配,刚开始i=0,j=0,needle[j]与haystack[i]进行比较,直到i=5时,needle[5]与haystack[5]不相等,此时将i指向索引为prefix[5]的位置。
  2. 此时发现prefix[5]之前是匹配成功的,不用管,直接从索引为prefix[5]的位置继续往后比较,直到如图a->b匹配失败,就回到prefix[1]的位置
  3. 当出现prefix的值为-1时,那么i,j同时往后移动一位,继续上面的操作。
  4. 当i的值小于等于(origin.Length - pattern.Length)时跳出上面的循环。

完整过程

那么如何生成prefix表?

qaq 自己明白容易,讲出来挺难额…

代码实现

static int KMP(string origin,string pattern)
{
    if (origin.Length < pattern.Length) return -1;
    else if (pattern.Length == 0) return 0;
    else if (origin == pattern) return 0;

    int[] prefix = new int[pattern.Length];

    //初始化Prefix表
    int pivit = 0;
    for (int i = 1; i < pattern.Length; i++)
    &#123;
        if (pattern[pivit] == pattern[i])
        &#123;
            ++pivit;
            prefix[i] = pivit;
        &#125;
        else
        &#123;
            pivit = 0;
            prefix[i]=0;
        &#125;
    &#125;

    //prefix 数据后移一位,prefix[0] = -1
    for (int i = prefix.Length - 1; i > 0; i--)
        prefix[i] = prefix[i - 1];
    prefix[0] = -1;

    //KMP查找
    int index = 0;
    int jndex = 0;
    while (index <= origin.Length - pattern.Length)
    &#123;
        if (jndex == pattern.Length-1)
            return index = jndex;
        if (origin[index] == pattern[jndex] || prefix[index]==-1)
        &#123;
            ++index;
            ++jndex;
        &#125;
        else
        &#123;
            jndex = prefix[jndex];
        &#125;
    &#125;
    return -1;
&#125;

参考

写博客不易,请我喝杯咖啡?

评论

arrow_upward