【LeetCode】字符串匹配

小咪咪 2024-04-24 20:35 37阅读 0赞

>  *  个人主页：[北·海][Link 1]
>  *  ?CSDN新晋作者
>  *  ?欢迎 ?点赞✍评论⭐收藏
>  *  ✨收录专栏：[C/C++][C_C]
>  *  ?希望作者的文章能对你有所帮助，有不足的地方请在评论区留言指正，大家一起学习交流！?

--------------------

![011a80a59e7c476c9794da7e50cf33e7.png][]

*  字符串匹配问题
    
     *  常见的字符串匹配算法包括暴力匹配、 Knuth-Morris-Pratt 算法、Boyer-Moore算法、Sunday 算法等
 *  解题 思路 1:
    
     *  两个指针各指向两个字符串的起始位置,先判断,两个字符串的第一个字符是否相同,如果相同的话,则将两个指针往下移动,并且判断较短字符串的下一个字符是否为空,如果为空,直接返回事先声明的index角标,如果不相等的话,则将较短指针的指向置为初始位置,将较长字符串的指向 = 上一次起始的角标 + 1,再将上一次起始的角标加一进行更新

class Solution {
    public:
        int strStr(string haystack, string needle) {
        int p1=0,p2=0;
        int index = 0;
        while(p1 < haystack.length()){
            if(needle[p2] ==  haystack[p1]){
                if(needle[p2+1] == '\0') {
                    return index;
                }
                p2++;
                p1++;
            }
            else{
                p2 = 0;
                p1 = index+1;
                index++;
            }
        }
        return -1;
        }
    };

解法 思路 2:

*  思路及算法
    
    我们可以让字符串needle 与字符串 haystack 的所有长度为 m 的子串均匹配一次。
    
    为了减少不必要的匹配，我们每次匹配失败即立刻停止当前子串的匹配，对下一个子串继续匹配。如果当前子串匹配成功，我们返回当前子串的开始位置即可。如果所有子串都匹配失败，则返回 −1。

class Solution {
    public:
        int strStr(string haystack, string needle) {
            int n = haystack.size(), m = needle.size();
            for (int i = 0; i + m <= n; i++) {
                bool flag = true;
                for (int j = 0; j < m; j++) {
                    if (haystack[i + j] != needle[j]) {
                        flag = false;
                        break;
                    }
                }
                if (flag) {
                    return i;
                }
            }
            return -1;
        }
    };

[Link 1]: https://blog.csdn.net/weixin_73865721?spm=1010.2135.3001.5343
[C_C]: https://blog.csdn.net/weixin_73865721?type=blog
[011a80a59e7c476c9794da7e50cf33e7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/24/c580afc512884de9a09cfcc746d72169.png