【C++】【LeetCode】KMP算法

2021/12/24 20:37:12

编程Tag： string return int C++ next size LeetCode KMP needle

本文主要是介绍【C++】【LeetCode】KMP算法，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

KMP算法

28. 实现 strStr()【简单，KMP】

image-20211224171547980

思路一：BF法，即朴素匹配，暴力破解

时间复杂度：O(nm)

空间复杂度：O(1)

class Solution {
public:
	int strStr(string haystack, string needle) {
		if (needle.size() > haystack.size()) return -1;   //排除子串比主串长的情况
		if (needle.size() == 0) return 0;                 //排除子串为空串的情况

		int i = 0, j = 0;
		while (i < haystack.size() && j < needle.size()) {
			if (haystack[i] == needle[j]) {         //1.两字符相等则继续匹配
				i++;
				j++;
			}
			else {  //主串起始位置右移，子串置位
				i = i - j + 1;   //移动一位再匹配
				j = 0;           //退回子串首位
			}
		}

		if (j == needle.size()) return i - j;     //2.子串中所有字符都匹配到了，就返回咯

		return -1; //未匹配到
	}
};

优化

//for循环比while循环性能好，主要体现在n-m上
class Solution {
public:
	int strStr(string haystack, string needle) {
		if (needle.size() == 0) return 0;

		int n = haystack.size(), m = needle.size();
		for (int i = 0; i <= n - m; i++) {               //注意这里的n-m  后面有子串比主串上的情况就不需要匹配了
			for (int j = 0; j < m; j++) {                //遍历子串
				if (haystack[i + j] != needle[j]) break; 

				if (j == m - 1) return i;                //子串全部匹配到
			}

		}

		return -1;
	}
};

思路二：KMP算法

字符串唯一一个难的算法，重点！！！

KMP算法视频讲解：https://www.bilibili.com/video/BV1PD4y1o7nd?spm_id_from=333.999.0.0

KMP算法文档讲解：参考代码随想录

前缀表：用来回退的，它记录了子串与主串不匹配的时候，子串应该从哪里开始重新匹配

KMP详解1

怎么制作前缀表：最长相等前后缀

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-a78bFmWK-1640348559509)(https://gitee.com/zdbya/picgo_image/raw/master/SSL_img/202112241725788.gif)]

前缀表记录的是不匹配时需要回退到哪里重新开始匹配

什么是next数组：next数组就是前缀表，但是很多实现都是把前缀表统一减1作为next数组；或者前缀表整体右移

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-vldCy8xZ-1640348559509)(https://gitee.com/zdbya/picgo_image/raw/master/SSL_img/202112241730223.gif)]

时间复杂度：O(n+m)

空间复杂度：O(m)，子串的长度，制作next数组

制作next数组

定义两个指针i和j，j指向前缀起始位置，i指向后缀起始位置。

统一减一版本

void getNext(int* next, const string& s){
    int j = -1;
    next[0] = j;
    for(int i = 1; i < s.size(); i++) { // 注意i从1开始
        while (j >= 0 && s[i] != s[j + 1]) { // 前后缀不相同了
            j = next[j]; // 向前回退
        }
        if (s[i] == s[j + 1]) { // 找到相同的前后缀
            j++;
        }
        next[i] = j; // 将j（前缀的长度）赋给next[i]
    }
}

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-RQA2sAVX-1640348559510)(https://gitee.com/zdbya/picgo_image/raw/master/SSL_img/202112241751184.gif)]

不减一版本

void getNext(int* next, const string& s) {
	int j = 0;
	next[0] = 0;
	for (int i = 1; i < s.size(); i++) {
		while (j > 0 && s[i] != s[j]) {
			j = next[j - 1];
		}
		if (s[i] == s[j]) {
			j++;
		}
		next[i] = j;
	}
}

前缀表统一减一 版本

class Solution {
public:
    //获取next数组的函数  统一-1版本
    void getNext(int* next, const string& s) {
        int j = -1;
        next[0] = j;
        for(int i = 1; i < s.size(); i++) { // 注意i从1开始
            while (j >= 0 && s[i] != s[j + 1]) { // 前后缀不相同了
                j = next[j]; // 向前回退
            }
            if (s[i] == s[j + 1]) { // 找到相同的前后缀
                j++;
            }
            next[i] = j; // 将j（前缀的长度）赋给next[i]
        }
    }
    
    int strStr(string haystack, string needle) {
        if (needle.size() == 0) return 0;   //排除特殊情况

        int next[needle.size()];
        getNext(next, needle);  //1.获取next数组
        
        int j = -1;                                         // 因为next数组里记录的起始位置为-1
        for (int i = 0; i < haystack.size(); i++) {         // 注意i就从0开始
            
            while(j >= 0 && haystack[i] != needle[j + 1]) { // 不匹配
                j = next[j];                                // j寻找之前匹配的位置
            }
            
            if (haystack[i] == needle[j + 1]) {             // 匹配，j和i同时向后移动
                j++;                                        // i的增加在for循环里
            }
            
            if (j == (needle.size() - 1) ) {                // 文本串s里出现了模式串t
                return (i - needle.size() + 1);
            }
        }
        
        return -1;
    }
};

前缀表不减一版本

背下来这个版本代码

class Solution {
public:
    void getNext(int* next, const string& s) {
        int j = 0;
        next[0] = 0;
        for(int i = 1; i < s.size(); i++) {
            while (j > 0 && s[i] != s[j]) {
                j = next[j - 1];
            }
            
            if (s[i] == s[j]) {
                j++;
            }
            next[i] = j;
        }
    }
    
    int strStr(string haystack, string needle) {
        if (needle.size() == 0) return 0;    //排除特殊情况

        int next[needle.size()];
        getNext(next, needle);                //1.获取next数组
        
        int j = 0;
        for (int i = 0; i < haystack.size(); i++) { 
            while(j > 0 && haystack[i] != needle[j]) {  // 不匹配
                j = next[j - 1];                        // j寻找之前匹配的位置
            }
            
            if (haystack[i] == needle[j]) {             // 匹配，j和i同时向后移动
                j++;
            }
            
            if (j == needle.size() ) {                  //子串匹配完成
                return (i - needle.size() + 1);
            }
        }
        
        return -1;
    }
};

459. 重复的子字符串【简单】

image-20211224182929322

方法一：暴力枚举

//时间复杂度：O(n^2)
//空间复杂度：O(1)

class Solution {
public:
	bool repeatedSubstringPattern(string s) {
		int n = s.size();
		for (int i = 1; i <= n/2; ++i) {   //枚举子串的长度
			if (n % i != 0) continue;      //主串的长度必须是子串长度的倍数

			for (int j = i; j < n; ++j) {   //遍历主串
				if (s[j] != s[j % i]) {     //串以i为一个周期
					break;
				}

				if (j == n - 1) return true;
			}
		}
		return false;
	}
};

方法二：字符串查找

/*
* 双倍字符串解决；
* 从索引1开始查找
* 查找单倍字符串的位置  是否在  第二个字符串开始的位置
* 是，则  false
* 否，则  true
*/
class Solution {
public:
	bool repeatedSubstringPattern(string s) {
		return (s + s).find(s, 1) != s.size();
	}
};

方法三：kmp实现方法二的find函数

需要掌握方法二的思路，然后用kmp做；在kmp基础上修改成这题能用的

class Solution {
public:
    void getNext(int* next, const string& s) {
        int j = 0;
        next[0] = 0;
        for (int i = 1; i < s.size(); i++) {
            while (j > 0 && s[i] != s[j]) {
                j = next[j - 1];
            }

            if (s[i] == s[j]) {
                j++;
            }
            next[i] = j;
        }
    }

    bool kmp(string haystack, string needle) {
        if (needle.size() == 0) return 0;    //排除特殊情况

        int next[needle.size()];
        getNext(next, needle);                //1.获取next数组

        int j = 0;
        for (int i = 1; i < haystack.size(); i++) {
            while (j > 0 && haystack[i] != needle[j]) {  // 不匹配
                j = next[j - 1];                        // j寻找之前匹配的位置
            }

            if (haystack[i] == needle[j]) {             // 匹配，j和i同时向后移动
                j++;
            }

            if (j == needle.size()) {                  //子串匹配完成
                if (i == haystack.size() - 1) {        //但是遍历完了主串
                    return false;
                }
                return true;
            }
        }

        return false;
    }

    bool repeatedSubstringPattern(string s) {
        return kmp(s + s, s);
	}
};

但是这题的next数组会有一个规律

image-20211224195311320

class Solution {
public:
    void getNext(int* next, const string& s) {
        int j = 0;
        next[0] = 0;
        for (int i = 1; i < s.size(); i++) {
            while (j > 0 && s[i] != s[j]) {
                j = next[j - 1];
            }

            if (s[i] == s[j]) {
                j++;
            }
            next[i] = j;
        }
    }

    bool repeatedSubstringPattern(string s) {
        if (s.size() == 0) return 0;    //排除特殊情况

        int next[s.size()];
        getNext(next, s);                //1.获取next数组
        
        int len = s.size();
        if(next[len-1] != 0 && len % (len - next[len-1]) == 0){
            return true;
        }
        
        return false;
	}
};

这便是最简洁的方法



这篇关于【C++】【LeetCode】KMP算法的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！


相关编程文章

更多>
本站官方QQ
官方QQ:
23002807

沪ICP备2023033072号-1

     

扫一扫关注最新编程教程