国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

算法設計 - 尋找一個字符串的重復子串LRS

shleyZ / 3025人閱讀

摘要：后綴數組最典型的是尋找一個字符串的重復子串字符串大小比較字符串大小比較是指字典順序，也就是對于兩個字符串。注意，在語言中，后綴數組記錄的也就是數組中的元素是一個字符指針，指向的是一個子串的起始字符。

雖是讀書筆記，但是如轉載請注明出處 http://segmentfault.com/blog/exploring/
.. 拒絕伸手復制黨

問題描述：

首先這是一個單字符串問題。子字符串 R 在字符串 L 中至少出現兩次，則稱 R 是 L 的重復子串。比如字符串abcdeabcd的LRS的長度是2，LRS是abcd

Longest Repeated Substring in GEEKSFORGEEKS is: GEEKS
Longest Repeated Substring in AAAAAAAAAA is: AAAAAAAAA
Longest Repeated Substring in ABCDEFG is: No repeated substring
Longest Repeated Substring in ABABABA is: ABABA
Longest Repeated Substring in ATCGATCGA is: ATCGA
Longest Repeated Substring in banana is: ana
Longest Repeated Substring in abcpqrabpqpq is: ab (pq is another LRS here)
一些定義：

后綴：后綴是指從某個位置i 開始到整個串末尾結束的一個特殊子串。字符串r 的從第i 個字符開始的后綴表示為Suffix(i)，也就是Suffix(i)=r[i..len(r)]。

后綴數組：后綴數組SA 是一個一維數組，它保存1..n 的某個排列SA[1]，SA[2]，...，SA[n]，并且保證Suffix(SA[i]) < Suffix(SA[i+1])，1≤i
也就是將S 的n 個后綴從小到大進行排序之后把排好序的后綴的開頭位置順次放入SA 中。
后綴數組最典型的是尋找一個字符串的重復子串

字符串大小比較： 字符串大小比較是指“字典順序”，也就是對于兩個字符串u、v。
令i 從1 開始順次比較u[i]和v[i]，如果u[i]=v[i]則令i 加1，否則若u[i]v[i]則認為u>v（也就是vlen(u)或者i>len(v)仍比較不出結果，那么若len(u)v。

方法1 ：

O(n^3) 直接子串和子串比較，查看所有字符串
比如 字符串 abcdabd, 先遍歷第一個元素a,從第二個開始找，找到某個跟他一樣的，開始游標k++,j++...然后記錄相等子串長度；然后遍歷第二個元素b開始...


public class LRS {
    private static int statLen(String X, int k, int j) {
        int cur_len = 0;

        while(k

方法2


使用后綴數組降低時間復雜度為O(n^2)

后綴數組的定義：一個字符數組，定義了一個字符串每個后綴子串的起始地址，如下圖是banana這個字符串的后綴數組：





可以使用Treeset 保存后綴數組的String們..


算法的主要思想



利用后綴數組實現記錄下來所有可能子串的起始地址，(用后綴數組的好處就是把所有起始位置相同的字符都放一起，就不用移動第二個指針 來找哪些字符與第一個指針指向的字符相同了 降低了一個n的維度的復雜度)


然后利用排序，把起始地址一致的字符放在一起：

這樣就簡化了暴力法當中通過移動j來控制下一個相同元素的過程，（也就是少了一層循環，同利用后綴數組的好處）因為相同的字符被放在了相鄰的位置，對以后綴數組的元素開始的子串兩兩比較就知道了重復子串的長度。


For example



比如上面那個banana例子，對banana的一次循環遍歷，得到后綴數組如上圖所示.


然后對其排序，我們就得到了:






這時候，遍歷后綴數組，每相鄰的子串就按照（下第二個圖comlen函數）的方法，計算兩個子串的公共長度。注意，在C++語言中，后綴數組記錄的（也就是數組中的元素）是一個字符指針，指向的是一個子串的起始字符。Java語言沒有指針，實現起來可能比較麻煩，看到別人的一種實現方式是利用Treeset，直接記錄所有后綴數組對應的子串，但是感覺空間開銷太大。





復雜度分析：


第一次遍歷原始數組，得到后綴數組的復雜度是O（n）, 對后綴數組的排序復雜度是O(nlogn)， 計算最長重復子串，遍歷后綴數組O（n）,每兩個相鄰元素的比較O（n）, 所以復雜度是O(n)+O(nlogn)+O(n^2) = O(n^2), 比暴力法的O（n^3）復雜度小，其主要的原因就是利用后綴數組這個數據結構緩存了每一個子串的起始位置，通過排序，避免了暴力法中通過j來定位的又一層循環~

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/64323.html

相關文章

  • 字符串處理文章outline

    摘要：遇到問題查查，看看，大神的講解問問島胖君下面是我最近整理出來的關于字符串的文章的怎么翻譯匯集目錄非常希望強化博客的功能，比如分類，置頂。 雖是讀書筆記，但是如轉載請注明出處 http://segmentfault.com/blog/exploring/ .. 拒絕伸手復制黨 最近在看算法和語言，基本屬于看知識 --> java實現 --> 整理blog 這個路線。 遇到問題查查st...

    Karuru 評論0 收藏0

  • JS算法題之leetcode(1~10)

    摘要：先去空白，去掉空白之后取第一個字符，判斷正負符號，若是英文直接返回，若數字則不取。回文數題目描述判斷一個整數是否是回文數。回文數是指正序從左向右和倒序從右向左讀都是一樣的整數。 JS算法題之leetcode(1~10) 前言 一直以來，前端開發的知識儲備在數據結構以及算法層面是有所暫缺的，可能歸根于我們的前端開發的業務性質，但是我認為任何的編程崗位都離不開數據結構以及算法。因此，我作為...

    SoapEye 評論0 收藏0

  • Leecode-3 Longest Substring Without Repeating Char

    摘要：題目解析題目含義很簡單，即求出沒有字符重復的子字符串的長度。例如很明顯就是個由完全重復字符組成的字符串，所以它的答案長度為。所以綜合來看該算法的效率為。 題目 Given a string, find the length of the longest substring without repeating characters. Example 1: Input: abcabcbbO...

    luzhuqun 評論0 收藏0

  • 前端算法題 | 這道題效率最高的算法，你可能不知道？

    摘要：當循環到的時候，記錄一下這個最后一次出現的位置在哪里。最后，這道算法題的出處來自里面有各種各樣的實現方法，可以作為參考。覺得本文對你有幫助請分享給更多人關注妙味前端加星標，關注更多內容 showImg(https://segmentfault.com/img/bVbj5DR?w=900&h=383); 尋找最長的不含有重復字符的子串 可能看標題不會明白這個題到底什么意思，來看看下面的例...

    zgbgx 評論0 收藏0

  • 尋找最長不重復子串

    摘要：尋找最長不重復子串思路時間復雜度為遍歷字符串，過程中將出現過的字符存入字典，為字符，為字符下標用保存遍歷過程中找到的最大不重復子串的長度用保存最長子串的開始下標如果字符已經出現在字典中，更新的值如果字符不在字典中，更新的值代碼本題以及其它 尋找最長不重復子串 Longest Substring Without Repeating Characters Given a string, ...

    afishhhhh 評論0 收藏0

發表評論

0條評論

shleyZ

男|高級講師

TA的文章

閱讀更多
最新活動
閱讀需要支付1元查看
<