??算法，不如說(shuō)它是一種思考方式??
算法專(zhuān)欄： ????123
一、??459. 重復(fù)的子字符串
- 題目描述：給定一個(gè)非空的字符串 s ，檢查是否可以通過(guò)由它的一個(gè)子串重復(fù)多次構(gòu)成。
- 來(lái)源：力扣（LeetCode）
- 難度：簡(jiǎn)單
- 提示：
1 <= s.length <= 104
s 由小寫(xiě)英文字母組成 - 示例 1:
輸入: s = “abab”
輸出: true
解釋: 可由子串 “ab” 重復(fù)兩次構(gòu)成。
示例 2:
輸入: s = “aba”
輸出: false
??解題
枚舉子字符串長(zhǎng)度
使用兩層 for 循環(huán)：
外層 for 遍歷子字符串長(zhǎng)度 i，所以遍歷的范圍是 1 ~ 字符串長(zhǎng)度一半，注意字符串長(zhǎng)度為 1 是不滿(mǎn)足返回 false。對(duì)于每一個(gè)子字符串長(zhǎng)度需要確定是否可以重復(fù)來(lái)構(gòu)成原字符串，即用字符串長(zhǎng)度對(duì)子字符串取余為 0。例如下圖字符串這種情況就會(huì)出現(xiàn)錯(cuò)誤判斷：
內(nèi)層 for 遍歷字符串 j，直到結(jié)束（j+i < s.length()），如下圖：
code:
class Solution {
public boolean repeatedSubstringPattern(String s) {
int n = s.length();
if(n==1)
return false;
boolean tag=false;
for(int i=1;i<=n/2;i++){//間隔
if(n%i!=0)
continue;
for(int j=0;j+i<n;j++){
if(s.charAt(j)!=s.charAt(j+i))
break;
if((j+i==n-1)&&(s.charAt(j)==s.charAt(j+i)))
tag=true;
}
if(tag==true)
break;
}
return tag;
}
}
一行代碼~
我們先看個(gè)例子：
字符串是：s1 = abc abc，我們可以看出是重復(fù)子字符串構(gòu)成的，如果我們把這個(gè)字符串復(fù)制追加到后面：s2 = abc abc abc abc，那么 s1 肯定是 s2 的一個(gè)子字符串，并且可以知道 s1 在 s2 中第 2 次出現(xiàn)的首個(gè)下標(biāo)號(hào)是在字符串 s1 的范圍內(nèi)。
字符串是：s2 = abcabac，不是重復(fù)子字符串構(gòu)成的：
是重復(fù)子字符串構(gòu)成的字符串，就表示字符串是可以拆解的：s = s’ + s’，那么 S = s + s = s’ + s’ + s’ + s’ ，即第二次出現(xiàn)的位置不會(huì)超過(guò)字符串 s 的長(zhǎng)度。(s + s).indexOf(s, 1)就是表示字符串 s 在 index = 1 開(kāi)始出現(xiàn)的下標(biāo)。
所以可以寫(xiě)出如下代碼：
class Solution {
public boolean repeatedSubstringPattern(String s) {
return (s + s).indexOf(s, 1) != s.length();
}
}
KMP 方法
有了前面一種解題方法，那我們使用 KMP 算法也容易理解了，就是在 S 中找有沒(méi)有子字符串 s，并且只能在 S 的前一半開(kāi)始的子字符串。
class Solution {
public boolean repeatedSubstringPattern(String s) {
return kmp(s + s, s);
}
public boolean kmp(String query, String pattern) {
int n = query.length();
int m = pattern.length();
int[] fail = new int[m];
Arrays.fill(fail, -1);
for (int i = 1; i < m; ++i) {
int j = fail[i - 1];
while (j != -1 && pattern.charAt(j + 1) != pattern.charAt(i)) {
j = fail[j];
}
if (pattern.charAt(j + 1) == pattern.charAt(i)) {
fail[i] = j + 1;
}
}
int match = -1;
for (int i = 1; i < n - 1; ++i) {
while (match != -1 && pattern.charAt(match + 1) != query.charAt(i)) {
match = fail[match];
}
if (pattern.charAt(match + 1) == query.charAt(i)) {
++match;
if (match == m - 1) {
return true;
}
}
}
return false;
}
}
對(duì)比上一個(gè)方法，在時(shí)間復(fù)雜度有了優(yōu)化。(s + s).indexOf(s, 1) 就是一種字符串的暴力解法，源碼：
public static int indexOf(byte[] value, int valueCount, byte[] str, int strCount, int fromIndex) {
byte first = str[0];
int max = (valueCount - strCount);
for (int i = fromIndex; i <= max; i++) {
// 找到第一個(gè)匹配的字符
if (value[i] != first) {
while (++i <= max && value[i] != first);
}
// 找后面匹配的字符
if (i <= max) {
int j = i + 1;
int end = j + strCount - 1;
for (int k = 1; j < end && value[j] == str[k]; j++, k++);
if (j == end) {
// 子字符串匹配，返回第一個(gè)字符的下標(biāo)
return i;
}
}
}
return -1;
}
public static int indexOfLatin1Unsafe(byte[] src, int srcCount, byte[] tgt, int tgtCount, int fromIndex) {
assert fromIndex >= 0;
assert tgtCount > 0;
assert tgtCount <= tgt.length;
assert srcCount >= tgtCount;
char first = (char)(tgt[0] & 0xff);
int max = (srcCount - tgtCount);
for (int i = fromIndex; i <= max; i++) {
// 找到第一個(gè)匹配的字符
if (getChar(src, i) != first) {
while (++i <= max && getChar(src, i) != first);
}
// 找后面匹配的字符
if (i <= max) {
int j = i + 1;
int end = j + tgtCount - 1;
for (int k = 1;
j < end && getChar(src, j) == (tgt[k] & 0xff);
j++, k++);
if (j == end) {
// 子字符串匹配
return i;
}
}
}
return -1;
}
返回第一頁(yè)。?
?物有本末，事有終始，知所先后。??
文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-441176.html
???????我的CSDN???????? 文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-441176.html
到了這里，關(guān)于LeetCode：459. 重復(fù)的子字符串 —【2、KMP算法】的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
