力扣 459. 重复的子字符串 kmp求循环节/思维

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

思路一：kmp，详见：https://blog.csdn.net/xiji333/article/details/88614354。

class Solution {
public:bool repeatedSubstringPattern(string s) {int siz=s.size();if(!siz)return 1;vector<int> next(siz+1);int k=-1,i=0;next[0]=-1;while(i<siz){if(k==-1||s[i]==s[k])next[++i]=++k;elsek=next[k];}return next[siz]>0&&siz%(siz-next[siz])==0;}
};

思路二：我们将原字符串$s$转换成$ss$，即拼接两次，然后从第$1$个位置开始查找字符串$s$出现的第一个位置，如果不等于$s.size$，那么就说明存在循环节。

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

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！