代码随想录day9 LeetCode 459重复的子字符串 字符串总结

459重复的子字符串

https://leetcode.cn/problems/repeated-substring-pattern/

class Solution {
public:
int* getNext(string s){//创建next[i]为最长相等前后缀长度的next数组
    int *next= new int[s.size()];
    int j=0;
    next[0]=0;
    for(int i=1;i<s.size();i++){
        while(j>0&&s[i]!=s[j]){
            j=next[j-1];
        }
        if(s[i]==s[j])++j;
        next[i]=j;
    }
    return next;
}
    bool repeatedSubstringPattern(string s) {
        int* next=getNext(s);
        int len=s.size();
         if(next[len-1]==0||len%(len-next[len-1])!=0)return 0;
        return 1;
    }
};

总结：

双指针法在字符串处理中比较常见，库函数reverse(s.begin(),s.end())注意参数里是迭代器，很多数组填充类的问题，都可以先预先给数组扩容带填充后的大小，然后在从后向前进行操作。erase的时间复杂度是O(n)尽量不要嵌套循环使用。