leetcode-repeated-substring-pattern

发表于   |   分类于 ，   |  

题目大意

　　https://leetcode.com/problems/repeated-substring-pattern/

　　判断字符串是否由其子串重复叠加拼接而成的

题目分析

　　利用kmp算法的构建辅助数组，可以回忆一下kmp算法中辅助数组含义是最长相同前缀和后缀。但是lps数组跟本题的关系是什么呢？考虑一下lps数组的最后一个值，最后一个代表整个字符串的最长前缀和后缀，如果等于0，那么一定得返回false。而且还要满足m % (m - lps[m - 1]) == 0，m - lps[m - 1]含义是除了最长前缀的后面的部分，如果字符串是重复一个字符串拼接多次而成，那么m - lps[m - 1]就是单独的一个“重复单元”，一定可以整除m。

代码

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
public class Solution {
    public boolean repeatedSubstringPattern(String str) {
        // 构造辅助lps数组
        char[] pat = str.toCharArray();
        int m = pat.length;
        int[] lps = new int[m];
        int i = 1;
        int preLen = 0;
        while (i < m) {
            if (pat[preLen] == pat[i]) {
                lps[i] = preLen + 1;
                preLen++;
                i++;
            } else {
                if (preLen == 0) {
                    lps[i] = 0;
                    i++;
                } else {
                    preLen = lps[preLen - 1];
                }
            }
        }
        // 判断
        return (lps[m - 1] > 0) && (m % (m - lps[m - 1]) == 0);
    }
}