KMP演算法 Java實現

来源:https://www.cnblogs.com/xiaofengs/p/18140402
-Advertisement-
Play Games

Problem: 28. 找出字元串中第一個匹配項的下標 目錄解題方法思路構建next數組回溯查找複雜度Code 解題方法 構建next串 回溯查找next串,最後下標 思路 通過最大首碼尾碼能找到下一次未查找到後要回溯的位置 構建next數組 無論如何第一個數的下一次回溯位置肯定是0,因此next ...


Problem: 28. 找出字元串中第一個匹配項的下標

目錄

解題方法

  1. 構建next串
  2. 回溯查找next串,最後下標

思路

  1. 通過最大首碼尾碼能找到下一次未查找到後要回溯的位置

構建next數組

無論如何第一個數的下一次回溯位置肯定是0,因此next[0]=0
這裡的 j表示首碼起始位置 i表示尾碼起始位置
如果找到字元不相同到的話,就讓他一直回溯找,並且回溯賦值j = next[j-1]
能找到相同字元的話就直接i++,j++,並且把next[i] = j
這裡先寫while判斷不相同 後寫相同,是因為不相同的終點
一定是有相同的尾碼或者直接結束查找(到了字元串末尾)

回溯查找

其實和上面的思路差不多,不能查找相同字元就一直回溯,能的話就共同前進,直到j到了模式串長度
這時因為i也在前進,所以i的下標是 應該返回的下標+(匹配串的長-1)

複雜度

時間複雜度:

添加時間複雜度, 示例: $O(m+n)$

空間複雜度:

添加空間複雜度, 示例: $O(m)$

Code

class Solution {

    public int strStr(String haystack, String needle) {
        return new KMP(needle).search(haystack);
    }

    public class KMP {
        private String pattern;   // 模式串
        private int[] next;
        public KMP(String pattern){
            this.pattern = pattern;
            int m = pattern.length();
            // 創建next 數組
            next = new int[m];
            next[0] = 0;
            for(int i = 1,j=0; i < m; i++){
                while(j>0&&pattern.charAt(i)!=pattern.charAt(j)){
                    j = next[j-1];
                }
                if(pattern.charAt(i) == pattern.charAt(j)){
                    j++;
                }
                next[i] = j;
            }
        }

        public int search(String text){
            int j = 0;
            for(int i=0;i<text.length();i++){
                while(j>0&&text.charAt(i) != pattern.charAt(j)){
                    j = next[j-1];
                }
                if(text.charAt(i) == pattern.charAt(j)){
                    j++;
                }
                if(j == pattern.length()){
                    return i-pattern.length()+1;
                }
            }
            return -1;
        }
    }

}

您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • 用python開發的小紅書關鍵詞搜索軟體,採集欄位包含:關鍵詞, 頁碼, 筆記id, 筆記鏈接, 筆記標題, 筆記類型, 點贊數, 用戶id, 用戶主頁鏈接, 用戶昵稱。 ...
  • 目錄一、 sqlmock介紹二、安裝三、基本用法四、一個小案例五、Gorm 初始化註意點 一、 sqlmock介紹 sqlmock 是一個用於測試資料庫交互的 Go 模擬庫。它可以模擬 SQL 查詢、插入、更新等操作,並且可以驗證 SQL 語句的執行情況,非常適合用於單元測試中。 二、安裝 go g ...
  • shell腳本中的運算符和條件判斷: 一、算術運算符 在Shell腳本中,你可以使用各種運算符來執行數學運算、比較和邏輯操作。 計算方式: $[ ] $(( )) 例: a=$[(9+5)90] 列印輸出結果 ==> echo $a 二、條件判斷 判斷方式: test $a = 90 [ $a = ...
  • 目錄一、httptest1.1 前置代碼準備1.2 介紹1.3 基本用法二、gock2.1介紹2.2 安裝2.3 基本使用2.4 舉個例子2.4.1 前置代碼2.4.2 測試用例 一、httptest 1.1 前置代碼準備 假設我們的業務邏輯是搭建一個http server端,對外提供HTTP服務。 ...
  • 什麼是觀察者 觀察者模式的主要角色包括: 主題(Subject): 也稱為被觀察者或可觀察對象。它維護了一系列觀察者對象,並提供方法用於註冊、刪除和通知觀察者。當主題的狀態發生改變時,它會通知所有註冊的觀察者。 觀察者(Observer): 觀察主題的對象。觀察者定義了一個更新方法,主題在狀態改變時 ...
  • 在 Python 中,迭代器是一種非常好用的數據結構,其最大的優勢就是延遲生成,按需使用,從而大大提高程式的運行效率。而 itertools 作為 Python 的內置模塊,就為我們提供了一套非常有用的用於操作可迭代對象的函數。 常用功能 1.count 功能詳解 count(start=0,ste ...
  • operator 模塊提供了一套與 Python 的內置運算符對應的高效率函數。 1.函數的種類 函數包含的種類有:對象的比較運算、邏輯運算、數學運算和序列運算 2.比較運算 運算 函數 語法 小於 lt(a, b) a < b 小於等於 le(a, b) a <= b 大於 gt(a, b) a ...
  • 試用阿裡雲GPU伺服器進行深度學習模型訓練 最近在用PyTorch時發現在本地訓練模型速度一言難盡,然後發現阿裡雲可以白嫖gpu伺服器,只要沒有申請過PAI-DSW資源的新老用戶都可以申請5000CU*H的免費額度,三個月內有效。 阿裡雲免費試用活動頁面 一、申請試用並創建實例 點擊試用,完成註冊、 ...
一周排行
    -Advertisement-
    Play Games
  • 下麵是一個標準的IDistributedCache用例: public class SomeService(IDistributedCache cache) { public async Task<SomeInformation> GetSomeInformationAsync (string na ...
  • 這個庫提供了在啟動期間實例化已註冊的單例,而不是在首次使用它時實例化。 單例通常在首次使用時創建,這可能會導致響應傳入請求的延遲高於平時。在註冊時創建實例有助於防止第一次Request請求的SLA 以往我們要在註冊的時候實例單例可能會這樣寫: //註冊: services.AddSingleton< ...
  • 最近公司的很多項目都要改單點登錄了,不過大部分都還沒敲定,目前立刻要做的就只有一個比較老的項目 先改一個試試手,主要目標就是最短最快實現功能 首先因為要保留原登錄方式,所以頁面上的改動就是在原來登錄頁面下加一個SSO登錄入口 用超鏈接寫的入口,頁面改造後如下圖: 其中超鏈接的 href="Staff ...
  • Like運算符很好用,特別是它所提供的其中*、?這兩種通配符,在Windows文件系統和各類項目中運用非常廣泛。 但Like運算符僅在VB中支持,在C#中,如何實現呢? 以下是關於LikeString的四種實現方式,其中第四種為Regex正則表達式實現,且在.NET Standard 2.0及以上平... ...
  • 一:背景 1. 講故事 前些天有位朋友找到我,說他們的程式記憶體會偶發性暴漲,自己分析了下是非托管記憶體問題,讓我幫忙看下怎麼回事?哈哈,看到這個dump我還是非常有興趣的,居然還有這種游戲幣自助機類型的程式,下次去大玩家看看他們出幣的機器後端是不是C#寫的?由於dump是linux上的程式,剛好win ...
  • 前言 大家好,我是老馬。很高興遇到你。 我們為 java 開發者實現了 java 版本的 nginx https://github.com/houbb/nginx4j 如果你想知道 servlet 如何處理的,可以參考我的另一個項目: 手寫從零實現簡易版 tomcat minicat 手寫 ngin ...
  • 上一次的介紹,主要圍繞如何統一去捕獲異常,以及為每一種異常添加自己的Mapper實現,並且我們知道,當在ExceptionMapper中返回非200的Response,不支持application/json的響應類型,而是寫死的text/plain類型。 Filter為二方包異常手動捕獲 參考:ht ...
  • 大家好,我是R哥。 今天分享一個爽飛了的面試輔導 case: 這個杭州兄弟空窗期 1 個月+,面試了 6 家公司 0 Offer,不知道問題出在哪,難道是杭州的 IT 崩盤了麽? 報名面試輔導後,經過一個多月的輔導打磨,現在成功入職某上市公司,漲薪 30%+,955 工作制,不咋加班,還不捲。 其他 ...
  • 引入依賴 <!--Freemarker wls--> <dependency> <groupId>org.freemarker</groupId> <artifactId>freemarker</artifactId> <version>2.3.30</version> </dependency> ...
  • 你應如何運行程式 互動式命令模式 開始一個互動式會話 一般是在操作系統命令行下輸入python,且不帶任何參數 系統路徑 如果沒有設置系統的PATH環境變數來包括Python的安裝路徑,可能需要機器上Python可執行文件的完整路徑來代替python 運行的位置:代碼位置 不要輸入的內容:提示符和註 ...