KMP算法

武大国重18年复试上机题目:KMP算法
祝自己顺利通过复试，加油！

字符串匹配是计算机基本任务之一，也是遥感数据处理中经常用到的。
Knuth-Morris-Pratt算法（简称KMP算法）是常用的算法之一。

部分匹配表

首先介绍下《部分匹配表》（Partial Match Table）的概念。

同时还有前缀和后缀的区别：

"部分匹配值"就是"前缀"和"后缀"的最长的共有元素的长度。以"ABCDABD"为例，

　　－　"A"的前缀和后缀都为空集，共有元素的长度为0；

　　－　"AB"的前缀为[A]，后缀为[B]，共有元素的长度为0；

　　－　"ABC"的前缀为[A, AB]，后缀为[BC, C]，共有元素的长度0；

　　－　"ABCD"的前缀为[A, AB, ABC]，后缀为[BCD, CD, D]，共有元素的长度为0；

　　－　"ABCDA"的前缀为[A, AB, ABC, ABCD]，后缀为[BCDA, CDA, DA, A]，共有元素为"A"，长度为1；

　　－　"ABCDAB"的前缀为[A, AB, ABC, ABCD, ABCDA]，后缀为[BCDAB, CDAB, DAB, AB, B]，共有元素为"AB"，长度为2；

　　－　"ABCDABD"的前缀为[A, AB, ABC, ABCD, ABCDA, ABCDAB]，后缀为[BCDABD, CDABD, DABD, ABD, BD, D]，共有元素的长度为0。

KMP算法

对于原字符串与搜索词，首先比较第一位，因为两者不匹配，所以原字符串后移一位。

因为B与A不匹配，继续后移。

现在出现了一个匹配字符，接着比较

两者还是相同。继续比较，直到出现不相同的字符为止。

image.png

自然状态下，我们可以通过暴力破解，采用两层循环进行匹配，但效率太低。
事实上，当空格与D不匹配时，前面6个已经匹配了，不需要返回搜索，因此我们可以记录这个信息，直接跳过前6个字符。

因此，其大致流程如下：

1. 原字符串与搜索词都从第一个字符开始匹配，若无匹配，则原字符串跳下一个；若有匹配，则继续匹配
2. 确定两者匹配的字符串数，若未完全匹配，则记录已匹配个数；若完全匹配，则记录匹配位置
3. 无论是否完全匹配，都将原字符串跳到上次匹配的末尾，继续匹配，直到整个原字符串匹配完毕。其中，跳跃的步数 = 已匹配的字数 - 其部分匹配值

编程实现

//KMP算法的实现

#include "stdafx.h"
#include<iostream>
#include<string>
#include<vector>

using namespace std;


int main()
{
    string ts, ps; //ts:待匹配串，ps：模式串
    cin >> ts >> ps;

    //计算next数组（部分匹配表）
    vector<int> next(ps.size(), 0); //next数组初始化
    for (size_t i = 1; i < ps.size(); i++)
    {
        string substr = ps.substr(0, i);//子串
        for (size_t j = 1; j < substr.size()-1; j++)
        {
            string strp = substr.substr(0, j);//前缀
            string stre = substr.substr(substr.size() - j, j);//后缀
            if (strp == stre)next[i - 1] = j;
        }
    }

    //KMP搜索
    for (size_t i = 0; i < ts.size(); i++)
    {//遍历ts
        for (size_t j = 0; j < ps.size(); j++)
        {//遍历ps
            if (ts[i + j] != ps[j]) break; //无匹配时跳出
            if (j + 1 == ps.size()) {//匹配长度为ps长度说明匹配到了
                cout <<"字符已匹配在："<< i + 1 << '\t' << endl;
                continue;
            }
            else {
                i += next[j];
            }
        }
    }

    system("pause");
    return 0;
}

本文参考:
http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html
https://blog.csdn.net/u011197534/article/details/78385547