1樓：王天賜
應該不需要擴充套件kmp。
直接執行kmp演算法，求出fail函式。對於任意乙個字首，可以根據它的長度和它結尾位置所對應的fail值求出這個字首的最小週期。然後檢查一下該字首的最小週期能不能整除字首長度的一半就好了（實際上是檢查長度的一半是不是乙個週期）
z-algorithm 和擴充套件kmp 的功能好像是一樣的，對於這道題應該更裸一點。
2樓：羊大王
座標電競大廠【VPGAME】World』s No.1 eSports service platform DOTA2，
主要思路：有兩個指標，head,tail，head = tail = 0,移動head，當head到head+4的字串為x=yy,進入判斷，tail = head+4 , tail ++,直到tail到tail+4的字串為x=yy時，head = tail,進入下一次迴圈
public class StringSearch {public static void main(String argsScanner scanner = new Scanner(new BufferedInputStream(System.inwhile(scanner.hasNextSystem.
out.println(getStr(scanner.nextLine(),"x=yy"static String getStr(String str, String prefixint headint tailint prefixLenhead = tail = 0String maxStr = nullprefixLen = prefix.
lengthif(str.length() < prefixLenreturn ""while(tail <= str.length() && head < str.
length() && tail < str.lengthif (head + prefixLen <= str.length() && prefix.
equals(str.substring(head, head + 4tail = head + prefixLenwhile (tail + prefixLen <= str.length() && !
prefix.equals(str.substring(tail, tail + 4tailif (maxStr == null || maxStr.
length() < str.substring(head, tail).lengthmaxStr = str.
substring(head, tailif (tail > str.length() - prefixLen && tail < str.lengthmaxStr = str.
substring(head, str.lengthhead = tailcontinueheadif(maxStr != nullreturn maxStrreturn ""
3樓：Radjedef
拓展kmp，extend[i]等於S[i]...S[n-1]與T[0...]的最長公共字首的長度
複雜度$O(n+m)$，，我看下面的suffix array，我感覺沒必要啊，$o(n)$實現常數大，dc3實現記憶體開銷大
Mathematica字串匹配的問題？
燕南 In 1 str Round 1 Aug 16 Arsenal 2 1 Crystal PLeicester 2 2 EvertonManchester U 1 2 SwanseaQPR 0 1 Hull Stoke 0 1 Aston VillaWest Bromwich 2 2 Sunde...
如何從幾十億字串（每個字串不超過200位元組）中，查詢出，包含某個子串所有字串
建議使用 KMP 演算法，如果是找出出現的位置，時間複雜度為 O 幾十億字串 的總長 某個子串 的長度 但題主問的是 包含某個子串所有字串 那這樣的字串就可以有很多個，而且你得輸出字串而不只是位置，那麼複雜度會大很多。最壞情況下，幾十億字串 中每乙個都是 200 個 a，某個子串 是乙個 a，那麼你...
C 字串比較是否相等
Sigon 你同事這種人還能有班上，作為即將踏進職場的畢業生感到非常難受。看看現在為了找個4千塊的實習都得刷一堆造航母難度的題。回到問題，之所以能得到正確結果是因為編譯器優化，將常量存在同乙個記憶體位址，而 比較的是兩個指標是否指向同乙個記憶體位址，所以得到了結果。你同事根本沒有理解C 邏輯，完全瞎...