代码随想录算法训练营第九天|28. 实现 strStr() 、459.重复的子字符串

发布时间:2024年01月19日

28. 实现 strStr()

思路:
1、暴力:将长字符串的每个字符开头的子字符串(长度为短字符串的长度)遍历与短字符串比较。
2、KMP(在一个长串中查找是否出现过另一个串)

暴力法代码实现

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

        return index;
    }
};

时间复杂度:O(nm)

459.重复的子字符串

思路:
双倍字符串的解法:字符串为s,将s+s得到双倍字符串,使用find()函数从下标为1的位置开始查找,若存在循环则会返回s以内字符的下标;否则返回第二个s的首字符下标。

代码实现

class Solution {
public:
    bool repeatedSubstringPattern(string s) {
        return (s+s).find(s, 1) < s.size();
    }
};

时间复杂度由string的find的时间复杂度决定,好像不同版本的编译器实现算法不同

文章来源:https://blog.csdn.net/heitong_fu/article/details/135705213
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。