题目描述

重复的子字符串459

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
import java.util.Scanner;

//重复的子字符串459
public class RepeatedSubstringPattern459 {
	public static void main(String[] args){
		Scanner input = new Scanner(System.in);
		System.out.print("请输入要判断寻找是不是重复子字符串的String = ");
		System.out.print("\n" + new Solution().repeatedSubstringPattern(input.nextLine()));
	}
}

class Solution {
    public boolean repeatedSubstringPattern(String s) {
    	if (s.equals("") == 0) {
    		return false;
    	}
    	int len = s.length();
    	int[] next = new int[len];
    	getNext(s, next);

    	if (next[len - 1] > 0 && len % (len - next[len - 1]) == 0) {
    		return true;
    	}
    	return false;
    }

    public void getNext(String s, int[] next) {
    	for (int j = 0, i = 1; i < s.length(); i++) {
    		while(j > 0 && s.charAt(j) != s.charAt(i)) j = next[j - 1];
    		if (s.charAt(j) == s.charAt(i)) j++;
    		if (j == s.length()) break;
    		next[i] = j; 
    	}
    }
}

个人总结

图四

正是因为 最长相等前后缀的规则，当一个字符串由重复子串组成的，最长相等前后缀不包含的子串就是最小重复子串。

上图是证明