用於在字符串中搜索子字符串的快速算法

Question

我想要一個可以在Java中用於搜索字符串中的子字符串的有效算法（或庫）。

我想要做的是：

給定的輸入字符串 - INSTR：

「BCDEFGH」

而且一組候選串 - CAND ：

「AB」， 「CDE」， 「FG」， 「H」， 「IJ」

找到任何CAND匹配的子字符串INSTR

中在這個例子中字符串我會匹配「CDE」，「FG」和「H」（但不是「AB」和「IJ」）

可能有很多候選字符串（在CAND中），但更重要的是我將執行此搜索數百萬次，所以我需要它快速。我想用char數組。另外，我並沒有將其構建爲解決方案，比如分發搜索 - 只是本地最有效的功能/算法。

此外，CAND和INSTR中的所有字符串都將相對較小（即字符數爲<），即目標字符串INSTR相對候選字符串不長。

---

更新我應該提到，集合CAND字符串是跨INSTR的所有值不變。

更新我只需要知道有一場比賽 - 我不需要知道比賽是什麼。

最終更新 我選擇嘗試AhoCorsick和拉賓卡爾普，由於簡單的實施。 因爲我有可變長度模式，所以我使用修改過的Rabin-Karp來散列每個模式的前n個字符，其中n是最小模式的長度，那麼N就是我的滾動子字符串搜索窗口的長度。 對於阿霍Corsick我用this

在我的測試中我兩個文件報紙文章搜索1000種模式，跨越1000次迭代等等均 標準化的完成時間爲：

AhoCorsick： 1

RabinKarp：1。8

樸素搜索（檢查每個圖案&使用string.contains）：

http://www.seas.gwu.edu/~simhaweb/cs151/lectures/module5/module5.html

http://www.cs.princeton.edu/courses/archive/spr09/cos226/lectures/18SubstringSearch-2x2.pdf：50個

---

*一些描述在下面的答案中提到的交易算法資源

http://www-igm.univ-mlv.fr/~lecroq/string/index.html *

Answer 1

請閱讀Aho-Corasick algorithm和Rabin-Karp algorithm。

如果輸入不是太大，你不希望多次重複搜索，也沒有多少模式，多次使用單個模式算法可能是一個好主意。 Wikipedia article on search algorithms給出了運行和預處理時間的許多算法。

實現：

• https://hkn.eecs.berkeley.edu/~dyoo/java/index.html
• http://algs4.cs.princeton.edu/53substring/RabinKarp.java.html
• https://github.com/hankcs/AhoCorasickDoubleArrayTrie
• https://github.com/RokLenarcic/AhoCorasick
• https://github.com/robert-bor/aho-corasick

簡報：

• http://www.slideshare.net/taka111/ahocorasick-string-matching-algorithm-15078438

Answer 2

將候選字符串集合轉換爲確定性有限狀態自動機，然後在線性時間內運行輸入字符串。將單個字符串轉換爲DFS在標準書籍中已有很好的介紹。您可以通過首先構造一個非確定性自動機然後確定它來轉換一組字符串。在最壞的情況下，這會導致機器人規模的指數式爆炸，但之後的搜索速度很快;特別是如果目標字符串很長，並且候選人短時間工作良好。

Answer 3

你可能要考慮Aho-Corasick algorithm和相關算法。我不知道任何實施這個的圖書館，但這是解決這個問題的經典方法。

Answer 4

Rabin-Karp multiple pattern search看起來是最快的。

Answer 5

另請參閱Boyer-Moore algorithm瞭解單串模式匹配。

Answer 6

這是正則表達式的用途。如上所述，有限狀態自動機是您需要的，但這正是如何實現標準的正則表達式匹配器。

在java中你可以寫這樣的：

StringBuilder sb = new StringBuilder(); 
bool first = true; 
for (String subStr : substrings) { 
    if (first) 
     first = false; 
    else 
     sb.append('|'); 
    sb.append(escape(subStr)); 
} 
Pattern p = Pattern.compile(sb.toString()); 

方法escape應該逃避它有一個正則表達式特殊含義的任何字符。

Answer 7

另一種解決方案是使用suffix array作爲INSTR。
由於INSTR很小，您可以使用冒泡排序對它進行排序。

之後您可以在O特定CAND串搜索（logN）的時間，
其中N =長度（suffix_array）=長度（INSTR）。

Answer 8

我們可以利用字符串的小尺寸（< 50個字符）爲這種情況構建一個超快速算法，代價是內存。

我們可以散列一次所有可能的INSTR子字符串，一次耗費O（n^2）次。然後，無論CAND字符串的數量如何，查找都將是O（1）。值得用於非常大量的CAND字符串。

如果INSTR很大，那麼我們可以構建一個後綴數組並且不對其進行排序，這樣頂部項目是最長的（= N），最下面的項目是INSTR的最後一個字符。現在對於每個CAND字符串，只要從頂部搜索長度（CAND）< =長度（後綴）。每個比較將是O（n）。

Answer 9

Here是Java中快速字符串搜索算法的一些實現。

Answer 10

import java.util.Scanner; 

public class StringMatch 
{ 
    static int temp,i=0,j=0; static boolean flag=true,matcher=false; 

    static String str=null,mstr=null;static char astr[],amstr[]; 

    static void getter(){ 
     Scanner sc = new Scanner(System.in); 
     str = sc.nextLine(); 
     //String str="today is Monday"; 
     astr=str.toCharArray(); 
     mstr = sc.nextLine(); 
     //String mstr="is"; 
     amstr=mstr.toCharArray(); 
    } 

    static void stringMatch(){ 
     while(i<astr.length){ 
      if(astr[i]==amstr[j]){ 
      while((j!=amstr.length)&&flag){temp=i; 
       if(astr[i]!=amstr[j]) {flag=false;matcher=false;} 
       else{matcher=true;} 
       i++;j++; 
       //System.out.println(i+"\t"+j); 
      }if(matcher==true)break;i=temp;}i++;j=0;flag=true; 

     } 
     if(matcher==true) {System.out.println("true");} 
     else {System.out.println("false");} 
    } 

    public static void main(String[] args) { 

    StringMatch.getter(); 
    StringMatch.stringMatch(); 

    } 
}