成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

459. Repeated Substring Pattern

Y3G / 1657人閱讀

摘要：題目鏈接利用求數(shù)組的方法來做，利用自身的重復(fù)性，表示在中，最大的使得參考視頻所以如果這個是呈現(xiàn)的樣子的話，假設(shè)的大小是，則并且根據(jù)可知，一旦中間出現(xiàn)不滿足的情況，，所以必然不是的，如果結(jié)尾處少了的話，例如，雖然，但

459. Repeated Substring Pattern

題目鏈接：https://leetcode.com/problems...

利用kmp求prefix數(shù)組的方法來做，利用string自身的重復(fù)性，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是呈現(xiàn)repeated substring pattern的樣子的話，假設(shè)repeat的大小是m，則prefix[0] = prefix[1] = ... = prefix[m-1] = 0 并且prefix[n-1] = prefix[n-2] + 1 =... = prefix[m] + n-m-1 = n - m
根據(jù)n % m == 0可知：n%(n - prefix[n-1]) == 0，一旦中間出現(xiàn)不滿足pattern的情況，prefix[n-1] < n / 2，所以n-prefix[n-1] > n / 2必然不是n的divisor，如果結(jié)尾處少了的話，例如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;
    }
}

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/69889.html

相關(guān)文章

  • LeetCode 攻略 - 2019 年 7 月下半月匯總（100 題攻略）

    摘要：月下半旬攻略道題，目前已攻略題。目前簡單難度攻略已經(jīng)到題，所以后面會調(diào)整自己，在刷算法與數(shù)據(jù)結(jié)構(gòu)的同時，攻略中等難度的題目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道題，目前已攻略 100 題。 一 目錄 不折騰的前端，和咸魚有什么區(qū)別...

    tain335 評論0 收藏0

  • 前端 | 每天一個 LeetCode

    摘要：在線網(wǎng)站地址我的微信公眾號完整題目列表從年月日起，每天更新一題，順序從易到難，目前已更新個題。這是項目地址歡迎一起交流學(xué)習(xí)。 這篇文章記錄我練習(xí)的 LeetCode 題目，語言 JavaScript。 在線網(wǎng)站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公眾號： showImg(htt...

    張漢慶 評論0 收藏0

  • 算法設(shè)計 - 尋找一個字符串的重復(fù)子串LRS

    摘要：后綴數(shù)組最典型的是尋找一個字符串的重復(fù)子串字符串大小比較字符串大小比較是指字典順序，也就是對于兩個字符串。注意，在語言中，后綴數(shù)組記錄的也就是數(shù)組中的元素是一個字符指針，指向的是一個子串的起始字符。 雖是讀書筆記，但是如轉(zhuǎn)載請注明出處 http://segmentfault.com/blog/exploring/ .. 拒絕伸手復(fù)制黨 問題描述： 首先這是一個單字符串問題。子字符...

    shleyZ 評論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 評論0 收藏0

  • 395. Longest Substring with At Least K Repeating C

    摘要：題目要求找出字符串中的最長子字符串，滿足該子字符串中任何字符出現(xiàn)的次數(shù)都大于。思路和代碼這是一個經(jīng)典的分治法解決的問題，關(guān)鍵在于我們?nèi)绾螌⑦@個問題分解為更小的子問題。 題目要求 Find the length of the longest substring T of a given string (consists of lowercase letters only) such th...

    vvpvvp 評論0 收藏0

發(fā)表評論

0條評論

最新活動
閱讀需要支付1元查看
<