字符串|459.重复的子字符串

本文主要是介绍字符串|459.重复的子字符串，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

力扣题目链接

class Solution {
public:void getNext (int* next, const string& s){next[0] = -1;int j = -1;for(int i = 1;i < s.size(); i++){while(j >= 0 && s[i] != s[j + 1]) {j = next[j];}if(s[i] == s[j + 1]) {j++;}next[i] = j;}}bool repeatedSubstringPattern (string s) {if (s.size() == 0) {return false;}int next[s.size()];getNext(next, s);int len = s.size();if (next[len - 1] != -1 && len % (len - (next[len - 1] + 1)) == 0) {return true;}return false;}
};

 这题还是使用KMP算法

对于KMP算法的难点，我想就是next数组这里了，用代码实现也确实不好理解。

步骤一：因为 这是相等的前缀和后缀，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] 相同。

总结

对于KMP算法自己要能够手动独立写出来，并且分析过程。

所以还是要多看再加深理解啊啊啊！

这篇关于字符串|459.重复的子字符串的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---