459. Repeated Substring Pattern

Y3G 发布于2019-08-16 10:29 / 1518人阅读

摘要：题目链接利用求数组的方法来做，利用自身的重复性，表示在中，最大的使得参考视频所以如果这个是呈现的样子的话，假设的大小是，则并且根据可知，一旦中间出现不满足的情况，，所以必然不是的，如果结尾处少了的话，例如，虽然，但

459. Repeated Substring Pattern

题目链接：https://leetcode.com/problems...

利用kmp求prefix数组的方法来做，利用string自身的重复性，prefix[i] = k, k < i表示在s[0, i+1]中，最大的k使得s[0, k] == s[i-k+1, i+1]
参考视频：
https://www.youtube.com/watch...

所以如果这个string是呈现repeated substring pattern的样子的话，假设repeat的大小是m，则prefix[0] = prefix[1] = ... = prefix[m-1] = 0 并且prefix[n-1] = prefix[n-2] + 1 =... = prefix[m] + n-m-1 = n - m
根据n % m == 0可知：n%(n - prefix[n-1]) == 0，一旦中间出现不满足pattern的情况，prefix[n-1] < n / 2，所以n-prefix[n-1] > n / 2必然不是n的divisor，如果结尾处少了的话，例如abcabca，虽然prefix[n-1] > n/2，但不满足divisor的条件。

public class Solution {
    public boolean repeatedSubstringPattern(String str) {
        int[] prefix = build(str);
        int n = str.length();
        return prefix[n-1] != 0 && n % (n - prefix[n-1]) == 0;
    }
    
    private int[] build(String s) {
        int n = s.length();
        int[] res = new int[n];
        int i = 1, j = 0;
        while(i < n) {
            // match, add the length
            if(s.charAt(i) == s.charAt(j)) {
                res[i] = j + 1;
                i++; j++;
            }
            // not match, return to previous
            else {
                if(j == 0) i++;
                else j = res[j-1];
            }
        }
        return res;
    }
}

云服务器私有云 459美元 Repeated Pattern Substring

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/69889.html

LeetCode 攻略 - 2019 年 7 月下半月汇总（100 题攻略）

摘要：月下半旬攻略道题，目前已攻略题。目前简单难度攻略已经到题，所以后面会调整自己，在刷算法与数据结构的同时，攻略中等难度的题目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道题，目前已攻略 100 题。一目录不折腾的前端，和咸鱼有什么区别...

tain335 2019-08-26 10:28 评论0 收藏0
前端 | 每天一个 LeetCode

摘要：在线网站地址我的微信公众号完整题目列表从年月日起，每天更新一题，顺序从易到难，目前已更新个题。这是项目地址欢迎一起交流学习。这篇文章记录我练习的 LeetCode 题目，语言 JavaScript。在线网站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公众号： showImg(htt...

张汉庆 2019-08-23 13:42 评论0 收藏0
算法设计 - 寻找一个字符串的重复子串LRS

摘要：后缀数组最典型的是寻找一个字符串的重复子串字符串大小比较字符串大小比较是指字典顺序，也就是对于两个字符串。注意，在语言中，后缀数组记录的也就是数组中的元素是一个字符指针，指向的是一个子串的起始字符。虽是读书笔记，但是如转载请注明出处 http://segmentfault.com/blog/exploring/ .. 拒绝伸手复制党问题描述：首先这是一个单字符串问题。子字符...

shleyZ 2019-08-14 12:09 评论0 收藏0
[LeetCode] 686. Repeated String Match

Problem Given two strings A and B, find the minimum number of times A has to be repeated such that B is a substring of it. If no such solution, return -1. For example, with A = abcd and B = cdabcdab. ...

ashe 2019-08-16 13:34 评论0 收藏0
395. Longest Substring with At Least K Repeating C

摘要：题目要求找出字符串中的最长子字符串，满足该子字符串中任何字符出现的次数都大于。思路和代码这是一个经典的分治法解决的问题，关键在于我们如何将这个问题分解为更小的子问题。题目要求 Find the length of the longest substring T of a given string (consists of lowercase letters only) such th...

vvpvvp 2019-08-16 15:09 评论0 收藏0