手机网站 数据库,微擎应用市场,网络公司经营范围怎么写,纪检监察网站建设方案给定一个非空的字符串 s #xff0c;检查是否可以通过由它的一个子串重复多次构成。
示例 1:
输入: s abab
输出: true
解释: 可由子串 ab 重复两次构成。示例 2:
输入: s aba
输出: false示例 3:
输入: s abcabcabcabc检查是否可以通过由它的一个子串重复多次构成。
示例 1:
输入: s abab
输出: true
解释: 可由子串 ab 重复两次构成。示例 2:
输入: s aba
输出: false示例 3:
输入: s abcabcabcabc
输出: true
解释: 可由子串 abc 重复四次构成。 (或子串 abcabc 重复两次构成。)
解题思路 1.如果s存在重复字串则将t掐头去尾以后一定还存在一个s 2.先去掉t的首尾字符(下标从1开始到length-2结束) 3.找t中是否存在一个s。
public class title459 {public static void main(String[] args) {String sababab;boolean result repeatedSubstringPattern(s);System.out.println(result);}public static boolean repeatedSubstringPattern(String s) {String tss;int j0;int[] nextgetNext(s);for(int i1;it.length()-1;i) {while(j0 t.charAt(i)!s.charAt(j)) {jnext[j-1];}if(t.charAt(i)s.charAt(j)) {j;}if(js.length()){return true;}}return false;}//求next数组public static int[] getNext(String s) {int[] next new int[s.length()];int j0;next[0]0;for(int i1;is.length();i) {while(j0 s.charAt(i)!s.charAt(j)) {jnext[j-1];}if(s.charAt(i)s.charAt(j)) {j;}next[i]j;}return next;}}
