KMP算法

1. 最简单的字符串匹配

记录两初始指针从前往后移动，匹配成功则一起后移
匹配失败则模板串指针回到首位，被匹配串指针移到上一次上一次初始匹配的下一位置
直至模板串匹配完返回真，或者被匹配串匹配完返回假，时间复杂度为O(mn)

class Solution {
public:
    int strStr(string haystack, string needle) {
        if(needle.size()==0) return 0;//空串
        int i =0, j =0;//因为还会用到，所以不能在循环中定义
        while(i

2. KMP算法

暴力匹配的优化，实际上改进了匹配失效后，主串指针回溯的距离，减少遍历次数
核心是对模板串进行评估，记录匹配任意一位匹配失效需要回溯的距离（位置），空间换时间
时间复杂度为O(m+n)，使算法性能成线性
具体方法是利用模板串本身结构特点，使得已遍历的信息不用再次确认，即用这种结构记录了已遍历信息

利用PM表对模板串评估，记录当下最长相等前缀数，如果某一位匹配失效，其所在最长相等前缀这部分则无需比较
直接移动跳过这些字符即可，即移动位数 = 已匹配字符数 - 对应部分匹配值（PM）
PM表也可以经过了一些修正，比如全体右移，这样就能直接用匹配失效的位置直接计算
其实一开始记录的是匹配失效时另一指针的位置即可

每次循环移动主串指针一位 
class Solution {
public:
    int strStr(string haystack, string needle) {
        int n = haystack.size(), m = needle.size();
        if (m == 0) return 0;
        vector next(m);//分配内存存储PM表
        get_next(needle,next);//获取PM表

        for (int i = 0, j = 0; i < n; i++) {//无脑遍历主串即可，一次遍历处理一位主串，可能移动多次子串
            while (j > 0 && haystack[i] != needle[j]) //
                j = next[j - 1];//匹配失效，重复转移和比较操作，直至相等或转移到首位
            if (haystack[i] == needle[j])
                j++;//相等的话移动子串指针
            if (j == m) //匹配成功
                return i - m + 1;
        }
        return -1;
    }
    void get_next(string needle,vector& next){
        for (int i = 1, j = 0; i < needle.size(); i++) {//一前一后两指针
            while (j > 0 && needle[i] != needle[j]) //匹配失效时
                j = next[j - 1]; //转移到匹配失效时应转移位置，也就是前一公共前缀末位置的下一位，重复转移和比较，直至相等或转移到首位
            if (needle[i] == needle[j]) 
                j++;//直到相等时，移动子串指针
            next[i] = j;//记录匹配失效子串指针应转移位置,因为这里另一指针还没移动，使用PM表示，指针应该减一
        }
    }
};

每次循环移动主串指针或子串指针一位 
class Solution {
public:
    int strStr(string haystack, string needle) {
        int n = haystack.size(), m = needle.size();
        if (m == 0) return 0;
        vector next(m);//分配内存存储PM表
        get_next(needle,next);//获取PM表

        int i = 0; int j = 0;
        while(i& next){
        next[0] = -1;//用于判断首位匹配失效
        for (int i = 0, j = -1; i < needle.size()-1;) {
           if(j==-1||needle[j]==needle[i]){
               i++;j++;//同时移动指针
               next[i]=j;//记录匹配失效应该转移转移位置
           }
           else j=next[j];//重置子串指针
        }
    }
};

3. 优化KMP

优化PM表的建立 
class Solution {
public:
    int strStr(string haystack, string needle) {
        int n = haystack.size(), m = needle.size();
        if (m == 0) return 0;
        vector next(m);//分配内存存储PM表
        get_next(needle,next);//获取PM表

        int i = 0; int j = 0;
        while(i& next){
        next[0] = -1;
        for (int i = 0, j = -1; i < needle.size()-1;) {
           if(j==-1||needle[j]==needle[i]){
               i++;j++;//同时移动指针
               if(needle[j]!=needle[i])
               next[i]=j;//记录转移失效转移位置
               else next[i]=next[j];
           }
           else j=next[j];
        }
    }
};
经典算法

相关

十大经典算法-冒泡排序及优化方法（java实现）

标签