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

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(); 

    } 
}