前要推理
以abababab为例,这里最主要的就是根据相等前后缀进行推导
s [ 0123 ]
如 t【 0123 】
f 【01 23 】
后两个分别是前后缀,第一个是总的字符串,然后可以推导
//首先还是算出 next数组,作为最长前后缀相等的最大长度 ;其次,是根据。前后缀的特性
s[01]=t[01]
t[01]=f[01]
t[23]=s[23]=f[01]
s[01]=s[23]
伪
具体详解:
步骤一:因为 这是相等的前缀和后缀,t[0] 与 k[0]相同, t[1] 与 k[1]相同,所以 s[0] 一定和 s[2]相同,s[1] 一定和 s[3]相同,即:,s[0]s[1]与s[2]s[3]相同 。
步骤二: 因为在同一个字符串位置,所以 t[2] 与 k[0]相同,t[3] 与 k[1]相同。
步骤三: 因为 这是相等的前缀和后缀,t[2] 与 k[2]相同 ,t[3]与k[3] 相同,所以,s[2]一定和s[4]相同,s[3]一定和s[5]相同,即:s[2]s[3] 与 s[4]s[5]相同。
步骤四:循环往复。
所以字符串s,s[0]s[1]与s[2]s[3]相同, s[2]s[3] 与 s[4]s[5]相同,s[4]s[5] 与 s[6]s[7] 相同。
正是因为 最长相等前后缀的规则,当一个字符串由重复子串组成的,最长相等前后缀不包含的子串就是最小重复子串。
下面的则是代码了
代码实现
class Solution {
public:
void getnext(int *next,const string &s){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;}}
//首先还是算出 next数组,作为最长前后缀相等的最大长度 ;其次,是根据。前后缀的特性
//s[01]=t[01]
//t[01]=f[01]
//t[23]=s[23]=f[01]
//s[01]=s[23]
//递推下去 bool repeatedSubstringPattern(string s) {int next[s.size()];getnext(next,s);if(next[s.size()-1]&&s.size()%(s.size()-next[s.size()-1])==0){//如果总长度-最长相等前后缀的长度 即空开的长度 能被size整除,就是最小重复字串return true;} return false;}
};
总结
数组长度减去最长相同前后缀的长度相当于是第一个周期的长度,也就是一个周期的长度,如果这个周期可以被整除,就说明整个数组就是这个周期的循环。