java LeetCode題解KMP算法示例
更新時間：2023年10月19日 08:56:25 作者：健身的墨鏡
這篇文章主要為大家介紹了java LeetCode題解KMP算法示例,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進步,早日升職加薪
KMP算法
前綴表
前綴：包含首字母，不包含尾字母的所有子串
后綴：只包含尾字母，不包含首字母的所有子串
最長相等前后綴
例如aabaaf,其最長相等前后綴如下
a 0
aa 1
aab 0
aaba 1
aabaa 2
aabaaf 0
匹配過程
在匹配過程中如果遇到不匹配，就跳到以該位置的前一位置對應的最長相等前后綴為索引的位置繼續(xù)匹配
next數(shù)組
遇到?jī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]:要點 這種回退表示匹配不成功,那么就需要
回到記憶中已經(jīng)匹配的下一位接著比較
前后綴相同
s[i]==s[j] j++
更新
next[i]=j:即記錄相同位數(shù)
示例題目
459.重復的子字符串: 給定一個非空的字符串 s ，檢查是否可以通過由它的一個子串重復多次構成。
思路:使用KMP算法求解,這里利用到了next數(shù)組,也就是最長相等前后綴,為什么要找最長相等前后綴呢?因為在有重復子字符串的字符串中,最長相等前后綴除外的那部分,我們可以推導出是這部分組成了整個字符串,所以通過判斷原字符串的長度能否整除這部分字符串的長度就可以直接判斷了
public boolean repeatedSubstringPattern(String s) {
int[] next=new int[s.length()];
getnext(next,s);
if(next[s.length()-1]>0){//如果為0會導致能整除從而出錯
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算法示例的詳細內容，更多關于java KMP算法的資料請關注腳本之家其它相關文章！
相關文章
SpringBoot調用WebService接口方法示例代碼
這篇文章主要介紹了使用SpringWebServices調用SOAP?WebService接口的步驟,包括導入依賴、創(chuàng)建請求類和響應類、生成ObjectFactory類、配置WebServiceTemplate、調用WebService接口以及測試代碼,文中通過代碼介紹的非常詳細,需要的朋友可以參考下2025-02-02
Java實現(xiàn)Map集合二級聯(lián)動示例,需要的朋友可以參考下2014-03-03
這篇文章主要介紹了springboot多文件壓縮實現(xiàn)過程,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教2025-04-04
Java通過notify和wait實現(xiàn)線程間的通信功能
在軟件開發(fā)中,線程是實現(xiàn)并發(fā)執(zhí)行的重要手段,然而,線程之間的協(xié)作與通信卻是開發(fā)者必須重點考慮的挑戰(zhàn)之一,Java作為一種廣泛應用于多線程編程的語言,本文將深入探討Java中通過notify和wait實現(xiàn)線程間通信的機制,需要的朋友可以參考下2024-06-06
這篇文章主要介紹了java編程多線程并發(fā)處理實例解析，分享了相關代碼示例，小編覺得還是挺不錯的，具有一定借鑒價值，需要的朋友可以參考下2018-01-01
本文介紹了Spring中的事務管理,包括聲明式事務管理和和編程式事務管理,重點講解了聲明式事務管理和Spring AOP的關系,及Spring事務攔截器TransactionInterceptor的調用的,最后還釋了Spring事務的創(chuàng)建和使用的具體過程,以及解決了一些事務相關問題2026-05-05
SpringBoot中的starter是一種非常重要的機制,能夠拋棄以前繁雜的配置,將其統(tǒng)一集成進starter,應用者只需要在maven中引入starter依賴,SpringBoot就能自動掃描到要加載的信息并啟動相應的默認配置,本文通過案例講解SpringBoot?Starter的使用,感興趣的朋友一起看看吧2023-12-12
線程池ThreadPoolExecutor使用簡介與方法實例
今天小編就為大家分享一篇關于線程池ThreadPoolExecutor使用簡介與方法實例，小編覺得內容挺不錯的，現(xiàn)在分享給大家，具有很好的參考價值，需要的朋友一起跟隨小編來看看吧2019-03-03
Java的JDBC編程使用之連接Mysql數(shù)據(jù)庫
這篇文章主要給大家介紹了關于Java的JDBC編程使用之連接Mysql數(shù)據(jù)庫的相關資料,JDBC是一種用于執(zhí)行SQL語句的Java?API,可以為多種關系數(shù)據(jù)庫提供統(tǒng)一訪問,需要的朋友可以參考下2023-12-12
本文介紹了使用Java發(fā)送POST請求的方法,包括引用工具類、設置訪問地址、請求頭和json請求體,最后使用工具類發(fā)送請求并返回結果2026-05-05