java LeetCode題解KMP算法示例
KMP算法
前綴表
前綴：包含首字母，不包含尾字母的所有子串
后綴：只包含尾字母，不包含首字母的所有子串
最長(zhǎng)相等前后綴
例如aabaaf,其最長(zhǎng)相等前后綴如下
a 0
aa 1
aab 0
aaba 1
aabaa 2
aabaaf 0
匹配過程
在匹配過程中如果遇到不匹配，就跳到以該位置的前一位置對(duì)應(yīng)的最長(zhǎng)相等前后綴為索引的位置繼續(xù)匹配
next數(shù)組
遇到?jīng)_突后回退到相應(yīng)位置（即前綴表）
求next數(shù)組的過程：getnext（next，s）
初始化
前綴末尾j初始化為0,next[0]=0
i為后綴末尾
for(i=1;i<s.size();i++)
前后綴不同
連續(xù)回退過程(while):j>0 s[i]!=s[j]
這里連續(xù)回退
j=next[j-1]:要點(diǎn) 這種回退表示匹配不成功,那么就需要
回到記憶中已經(jīng)匹配的下一位接著比較
前后綴相同
s[i]==s[j] j++
更新
next[i]=j:即記錄相同位數(shù)
示例題目
459.重復(fù)的子字符串: 給定一個(gè)非空的字符串 s ，檢查是否可以通過由它的一個(gè)子串重復(fù)多次構(gòu)成。
思路:使用KMP算法求解,這里利用到了next數(shù)組,也就是最長(zhǎng)相等前后綴,為什么要找最長(zhǎng)相等前后綴呢?因?yàn)樵谟兄貜?fù)子字符串的字符串中,最長(zhǎng)相等前后綴除外的那部分,我們可以推導(dǎo)出是這部分組成了整個(gè)字符串,所以通過判斷原字符串的長(zhǎng)度能否整除這部分字符串的長(zhǎng)度就可以直接判斷了
public boolean repeatedSubstringPattern(String s) {
int[] next=new int[s.length()];
getnext(next,s);
if(next[s.length()-1]>0){//如果為0會(huì)導(dǎo)致能整除從而出錯(cuò)
if(s.length()%(s.length()-next[s.length()-1])==0){
return true;
}
}
return false;
}
public void getnext(int[] next,String s){
int j=0;
next[0]=0;
for (int i = 1; i < s.length(); i++) {
while(j>0&&s.charAt(i)!=s.charAt(j)){
j=next[j-1];
}
if(s.charAt(i)==s.charAt(j)){
j++;
}
next[i]=j;
}
}以上就是java LeetCode題解KMP算法示例的詳細(xì)內(nèi)容，更多關(guān)于java KMP算法的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！
相關(guān)文章
這篇文章主要介紹了Java封裝統(tǒng)一的Result Model案例，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過來看看吧2020-08-08
Java數(shù)據(jù)結(jié)構(gòu)-HashMap詳解
這篇文章主要介紹了Java數(shù)據(jù)結(jié)構(gòu)-HashMap，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2019-03-03
IDEA強(qiáng)制清除Maven緩存的實(shí)現(xiàn)示例
清除項(xiàng)目緩存是一個(gè)常見的操作,本文主要介紹了IDEA強(qiáng)制清除Maven緩存的實(shí)現(xiàn)示例,文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2024-07-07
Java線程的start方法回調(diào)run方法的操作技巧
面試過程中經(jīng)常會(huì)被面試官問到為什么我們調(diào)用start()方法時(shí)會(huì)執(zhí)行run()方法，為什么不能直接調(diào)用run()方法，問的一頭霧水，今天小編給大家介紹下Java線程的start方法回調(diào)run方法的操作技巧，需要的朋友參考下吧2017-11-11
springboot中pom.xml文件注入test測(cè)試依賴時(shí)報(bào)錯(cuò)的解決
這篇文章主要介紹了springboot中pom.xml文件注入test測(cè)試依賴時(shí)報(bào)錯(cuò)的解決，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2022-03-03
MyBatis實(shí)現(xiàn)動(dòng)態(tài)查詢、模糊查詢功能
這篇文章主要介紹了MyBatis實(shí)現(xiàn)動(dòng)態(tài)查詢、模糊查詢功能，非常不錯(cuò)，具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2018-06-06
如何使用spring-ws發(fā)布webservice服務(wù)
文章介紹了如何使用Spring-WS發(fā)布Web服務(wù),包括添加依賴、創(chuàng)建XSD文件、生成JAXB實(shí)體、配置Endpoint、啟動(dòng)服務(wù)等步驟,結(jié)合實(shí)例代碼給大家介紹的非常詳細(xì),感興趣的朋友跟隨小編一起看看吧2024-11-11
淺談Redis在微服務(wù)架構(gòu)中的幾種應(yīng)用場(chǎng)景
本文介紹在SpringCloud中使用Redis作為Pub/Sub異步通信、緩存或主數(shù)據(jù)庫和配置服務(wù)器的三種場(chǎng)景應(yīng)用。小編覺得挺不錯(cuò)的，現(xiàn)在分享給大家，也給大家做個(gè)參考。一起跟隨小編過來看看吧2019-05-05
Java8方法引用及構(gòu)造方法引用原理實(shí)例解析
這篇文章主要介紹了Java8方法引用及構(gòu)造方法引用原理實(shí)例解析,文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2020-09-09
Java中使用異或語句實(shí)現(xiàn)兩個(gè)變量的互換
這篇文章主要介紹了Java中使用異或語句實(shí)現(xiàn)兩個(gè)變量的互換,本文直接給出代碼實(shí)例以及運(yùn)行結(jié)果,需要的朋友可以參考下2015-06-06