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)尽量不要嵌套循环使用。
标签:459,return,int,随想录,len,next,字符串 From: https://www.cnblogs.com/zhishikele/p/17028938.html