数据结构和算法|[字符串]重复的子字符串 leetcode|数据结构

一、题目描述原文链接：459. 重复的子字符串

具体描述：
给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。
示例 1:

输入: s = “abab”
输出: true
解释: 可由子串 “ab” 重复两次构成。

示例 2:

输入: s = “aba”
输出: false

示例 3:

输入: s = “abcabcabcabc”
输出: true
解释: 可由子串 “abc” 重复四次构成。 (或子串 “abcabc” 重复两次构成。)

提示：

1 <= s.length <= 10^4
s 由小写英文字母组成

二、思路分析可以用KMP做呀！可以先看看KMP介绍！
第一步：求出next数组！

abab
next = {0, 0, 1, 2};

第二步：理解

字符串长度 % （len - 最后一个字符对应的最长前后缀长度）等于0，则说明是重复子字符串！

abab
4 % (4 - 2) = 0;
还真是等于0,为啥那？
因为2其实代表一个周期，4-2代表剩下的周期，4%（4-2）如果能被整除，那说明剩下的是一个周期，那一定是重复的子字符串！

三、AC代码

class Solution { public void getNext(int[] next, String s){ // 初始化 int j = 0; next[j] = j; int i = 1; for (i = 1; i < s.length(); i++){ // 前缀末尾不等于后缀末尾 while (j > 0 && s.charAt(i) != s.charAt(j)){ j = next[j - 1]; }// 前缀末尾等于后缀末尾 if (s.charAt(i) == s.charAt(j)){ j++; }// next[i] 赋值 next[i] = j; }} public boolean repeatedSubstringPattern(String s) { if (s.length() == 0) return false; int len = s.length(); int[] next = new int[len]; getNext(next, s); if (next[len - 1] != 0 && ( len % (len - next[len - 1]) == 0 )){ return true; }return false; } }

四、总结