KMP算法

解释: 判断一个字符串的子串是否为另一个字符串

思路:
- 规定:
  - Next数组: 一个字符串的某个字符最长前缀和最长后缀相等的长度
  - 最长前缀: 一个字符串某个字符前面的字符串由0到Length - 2位置形成的字符串
  - 最长后缀: 一个字符串某个字符前面的字符串由1到Length - 1位置形成的字符串
1. 构建Next数组
2. 开始从头匹配两个字符串
  - 如果相等, 两个字符串的索引下移
  - 如果不相等
    - 如果目标字符串索引为0, 源字符串索引下移
    - 如果目标字符串索引不为0, 目标字符串索引根据Next数组前移(解释: 因为最长前缀和最长后缀是相同的, 所以后面和最长后缀相同的地方, 最长前缀已经没有必要再进行匹配了, 所以不用目标字符串索引没有必要置0)
3. 匹配结束时, 判断目标字符串是否已匹配完
  - 如果匹配完成, 返回源字符串索引-目标字符串索引(解释: 因为此时源字符串的索引位置前面的目标字符串长度个字符恰好是目标字符串, 所以减去目标字符串索引或者目标字符串长度, 恰好是目标字符串在源字符串的位置)
  - 如果没有匹配完成, 返回-1
解释:
- 为什么可以目标字符串前移不会出错?
  - 假设源字符串从i到j位置匹配到了目标字符串的0到k的位置
  - 假设源字符串j+1位置的字符和目标字符串的k+1位置不相同
  - 这时候目标字符串要前移到最长前缀位置, 假设这个位置为m
  - 这时候也就是说等价于从源字符串的j-m到j位置匹配到了目标字符串的0到m位置
  - 相当于忽略源字符串i到j-m直接的匹配
  - 假设i到j-m中的某个字符开始的字符串可以匹配完成目标字符串, 假设这个字符索引是n
  - 那么我们可以得到源字符串的n到j与目标字符串的0到n位置相同
  - 又因为源字符串i到j和目标字符串0到k是匹配成功的
  - 所以可以得到源字符串的n到j和目标字符串k-n到k是相同的
  - 因为n是取的i到j-m之间的字符串, 所以j-n要大于m
  - 这时候目标字符串0到n, k-n到k位置的字符串相同, 并且长度为j-n
  - 我们发现如果这样的n如果存在, 我们会得到一个比Next数组中更大的最长前缀, 这显然与Next数组冲突, 所以在i到j-m位置是不会存在能匹配到目标字符串的位置的
- Next数组求值:
  - 规定索引0的位置值为-1
  - 规定索引1的位置值为0
  - 在求其他位置的Next值时
    - 记录上一个位置最长前缀的长度(比如索引2的时候, 长度为索引1的值, 即是0)
    - 判断上一个字符是否等于记录长度位置的字符是否相等
      - 相等, 当前位置的值为上一个位置的值+1, 记录的位置下移
      - 不相等, 记录位置的值变为记录位置作为索引时, Next数组的值(缩小已匹配的前缀)
  - 循环完成, 返回即可

代码:

public static int KMP(String source, String target)
{
    if (source == null || target == null)
    {
        return -1;
    }
    int[] nextArray = GetNextArray(target);
    int sIndex = 0, tIndex = 0;
    while (sIndex < source.Length && tIndex < target.Length)
    {
        if (source[sIndex] == target[tIndex])
        {
            sIndex++;
            tIndex++;
        }
        else
        {
            if (tIndex == 0)
            {
                sIndex++;
            }
            else
            {
                tIndex = nextArray[tIndex];
            }
        }
    }
    return tIndex == target.Length ? sIndex - tIndex : -1;
}
public static int[] GetNextArray(string str)
{
    if (String.IsNullOrEmpty(str))
    {
        return null;
    }
    int[] res = new int[str.Length];
    int cn = 0, index = 0;
    while (index < res.Length)
    {
        if (index == 0)
        {
            res[index++] = -1;
        }
        else if (index == 1)
        {
            res[index++] = 0;
        }
        else
        {
            if (str[cn] == str[index - 1])
            {
                res[index++] = ++cn;
            }
            else if (cn > 0)
            {
                cn = res[cn];
            }
            else
            {
                res[index++] = 0;
            }
        }
    }
    return res;
}