代码随想录算法训练营第九天| 28. 实现 strStr() 459.重复的子字符串 字符串总结 双指针回顾

 28. 实现 strStr()

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回  -1 。

题目链接：28. 找出字符串中第一个匹配项的下标 - 力扣（LeetCode）

思路：标标准准的kmp算法，可以我不会写，只能用土方法for循环了。

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

    }
};

似乎是把KMP看懂了，先把KMP算法放这里吧

class Solution {
public:
    int strStr(string s, string p) {
        int n = s.size(), m = p.size();
        if(m == 0) return 0;
        //设置哨兵
        s.insert(s.begin(),' ');
        p.insert(p.begin(),' ');
        vector<int> next(m + 1);
        //预处理next数组
        for(int i = 2, j = 0; i <= m; i++){
            while(j and p[i] != p[j + 1]) j = next[j];
            if(p[i] == p[j + 1]) j++;
            next[i] = j;
        }
        //匹配过程
        for(int i = 1, j = 0; i <= n; i++){
            while(j and s[i] != p[j + 1]) j = next[j];
            if(s[i] == p[j + 1]) j++;
            if(j == m) return i - m;
        }
        return -1;
    }
};

459.重复的子字符串

给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。

题目链接：459. 重复的子字符串 - 力扣（LeetCode）

思路：开始时认为本题可以根据字母出现次数来解决，结果发现不充要，因为所有字母（不为0的）出现次数存在共同公因数时未必有循环字符串，是必要不充分。只能老老实实用字符串处理了。

思路（真）：从2开始尝试子串重复次数，子串的重复次数应满足：1、2<=i<=字符串长度2、是字符串长度的因数。当找到可能得子串重复次数后，子串长度也能确定了。在按位确定子串是否循环至字符串末尾。效率竟然意外的不错。

class Solution {
public:
    bool repeatedSubstringPattern(string s) {
        int length=s.size();
        int cl;     //子串长度
        int i=2;    //子串重复次数
        while(i<=length){
            if(length%i)
            {
                ++i;continue;
            }
            cl=length/i;
            int k=1;                                //k*cl==按位比较时的偏移量
            for(int j=0;j<cl;j++){
                while(k<i&&s[j]==s[j+k*cl])++k;    //注意逻辑判断顺序不能更换
                if(k!=i)break;                     
                k=1;                               //勿忘重置k
                if(j==cl-1)return true;
                }
            i++;
            }
        return false;
        }
};

啊？