dede5.7 做的网站 下 加一个discuz论坛,公司介绍页面设计,企业网站首页图片,手机网站免费生成前要推理
以abababab为例#xff0c;这里最主要的就是根据相等前后缀进行推导 s [ 0123 ]
如 t【 0123 】 f 【01 23 】
后两个分别是前后缀#xff0c;第一个是总的字符串#xff0c;然后可以推导 //首先还是算出…前要推理
以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]相同。
步骤四循环往复。
所以字符串ss[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 j0;next[0]0;for(int i1;is.size();i){while(j0s[i]!s[j]){jnext[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;}
};
总结
数组长度减去最长相同前后缀的长度相当于是第一个周期的长度也就是一个周期的长度如果这个周期可以被整除就说明整个数组就是这个周期的循环。
