easy 实现 strStr() 双指针单指针 + 字符串切片双指针：单指针 + 字符串切片：KMP 算法

87 阅读 0 评论 58 点赞

我是靠谱客的博主超帅煎蛋，最近开发中收集的这篇文章主要介绍easy 实现 strStr() 双指针单指针 + 字符串切片双指针：单指针 + 字符串切片：KMP 算法，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

在这里插入图片描述

双指针：

c++

「朴素匹配」而言，一旦匹配失败，将会将原串指针调整至下一个「发起点」，匹配串的指针调整至起始位置，然后重新尝试匹配。「朴素匹配」的复杂度是
O(m*n)


class Solution {
public:
    int strStr(string haystack, string needle) {
        for(int i = 0; i + needle.size() <= haystack.size(); i++) {
            int j = 0;
            while(j < needle.size() && needle[j] == haystack[i + j]){
                 j++;
            }
            if(j == needle.size()){
                return i;
            }
        }
        return -1;
    }
};

单指针 + 字符串切片：

python


class Solution:
    def strStr(self, haystack: str, needle: str) -> int:
        if not needle:
            return 0

        left=0
        right = len(needle)
        while right <= len(haystack):
            if haystack[left:right] == needle:
                return left
            left += 1
            right += 1

        return -1

c++

c++ string 字符串切片 substr函数：string.substr(pos, n)


class Solution {
public:
    int strStr(string haystack, string needle) {
        if(needle.empty()){
            return 0;
        }
        
        int left=0;
        int right = needle.size();
        while((left+right) <= haystack.size()){
            if (haystack.substr(left, right) == needle){
                return left;
            }
            left++;
        }
        return -1;
    }
};