C++刷题 -- 字符串

C++刷题 – 字符串

1.重复的子字符串

https://leetcode.cn/problems/repeated-substring-pattern/submissions/490209402/
暴力解法
第一个for循环用来标定子串的末尾，根据末尾取出子串
第二个while循环用来检查原字符串是否由子串构成

class Solution {
public:
    bool repeatedSubstringPattern(string s) {
        for(int i = 0; i < s.size(); i++)
        {
            if(s.size() % (i + 1) != 0)
            {
                continue;
            }
            if(i >= s.size() / 2)
            {
                break;
            }
            string subStr = s.substr(0, i + 1);
            int length = i + 1;
            int pos = 0;
            while(pos < s.size())
            {
                if(subStr == s.substr(pos, length))
                {
                    pos += length;
                }
                else
                {
                    break;
                }
                if(pos == s.size())
                {
                    return true;
                }
            }
        }
        return false;
    }
};

• 时间复杂度: O(n^2)
• 空间复杂度: O(1)

移动匹配
当一个字符串s：abcabc，内部由重复的子串组成，那么这个字符串的结构一定是这样的：

也就是由前后相同的子串组成。

那么既然前面有相同的子串，后面有相同的子串，用 s + s，这样组成的字符串中，后面的子串做前串，前面的子串做后串，就一定还能组成一个s，如图：

所以判断字符串s是否由重复子串组成，只要两个s拼接在一起，里面还出现一个s的话，就说明是由重复子串组成。

当然，我们在判断 s + s 拼接的字符串里是否出现一个s的的时候，要刨除 s + s 的首字符和尾字符，这样避免在s+s中搜索出原来的s，我们要搜索的是中间拼接出来的s。

class Solution {
public:
    bool repeatedSubstringPattern(string s) {
        string t = s + s;
        t.erase(t.begin()); t.erase(t.end() - 1); // 掐头去尾
        if (t.find(s) != std::string::npos) return true; // r
        return false;
    }
};

• 时间复杂度: O(n)
• 空间复杂度: O(1)

不过这种算法最终还是要判断一个字符串中是由存在一个子串，该类库函数的实现可以使用KMP算法。