資訊專欄INFORMATION COLUMN
摘要：題目鏈接利用求數(shù)組的方法來(lái)做，利用自身的重復(fù)性，表示在中，最大的使得參考視頻所以如果這個(gè)是呈現(xiàn)的樣子的話，假設(shè)的大小是，則并且根據(jù)可知，一旦中間出現(xiàn)不滿足的情況，，所以必然不是的，如果結(jié)尾處少了的話，例如，雖然，但
459. Repeated Substring Pattern
題目鏈接：https://leetcode.com/problems...
利用kmp求prefix數(shù)組的方法來(lái)做，利用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...
所以如果這個(gè)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)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://www.ezyhdfw.cn/yun/69889.html
摘要：月下半旬攻略道題，目前已攻略題。目前簡(jiǎn)單難度攻略已經(jīng)到題，所以后面會(huì)調(diào)整自己，在刷算法與數(shù)據(jù)結(jié)構(gòu)的同時(shí)，攻略中等難度的題目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道題，目前已攻略 100 題。 一 目錄 不折騰的前端，和咸魚(yú)有什么區(qū)別...
摘要：在線網(wǎng)站地址我的微信公眾號(hào)完整題目列表從年月日起，每天更新一題，順序從易到難，目前已更新個(gè)題。這是項(xiàng)目地址歡迎一起交流學(xué)習(xí)。 這篇文章記錄我練習(xí)的 LeetCode 題目，語(yǔ)言 JavaScript。 在線網(wǎng)站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公眾號(hào)： showImg(htt...
摘要：后綴數(shù)組最典型的是尋找一個(gè)字符串的重復(fù)子串字符串大小比較字符串大小比較是指字典順序，也就是對(duì)于兩個(gè)字符串。注意，在語(yǔ)言中，后綴數(shù)組記錄的也就是數(shù)組中的元素是一個(gè)字符指針，指向的是一個(gè)子串的起始字符。 雖是讀書(shū)筆記，但是如轉(zhuǎn)載請(qǐng)注明出處 http://segmentfault.com/blog/exploring/ .. 拒絕伸手復(fù)制黨 問(wèn)題描述： 首先這是一個(gè)單字符串問(wèn)題。子字符...
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. ...
摘要：題目要求找出字符串中的最長(zhǎng)子字符串，滿足該子字符串中任何字符出現(xiàn)的次數(shù)都大于。思路和代碼這是一個(gè)經(jīng)典的分治法解決的問(wèn)題，關(guān)鍵在于我們?nèi)绾螌⑦@個(gè)問(wèn)題分解為更小的子問(wèn)題。 題目要求 Find the length of the longest substring T of a given string (consists of lowercase letters only) such th...
閱讀 2786·2021-10-12 10:12
閱讀 2395·2021-09-02 15:41
閱讀 2630·2019-08-30 15:55
閱讀 1469·2019-08-30 13:05
閱讀 2538·2019-08-29 11:21
閱讀 3601·2019-08-28 17:53
閱讀 3105·2019-08-26 13:39
閱讀 849·2019-08-26 11:50
