高速字符串匹配算法

Question

我基本上正在对一些高速字符串匹配算法进行基准测试，我发现了一些算法。

1. 高速反向不确定DAWG（有向无环字图）匹配算法，由Gonzalo Navarro和Mathieu Raffinot制定。请参阅“A Bit-Parallel Approach to Suffix Automata: Fast Extended String Matching”

2. Horspool改进的Boyer-Moore字符串搜索算法。请参阅“Practical fast searching in strings”

3. 带有不匹配项的Shift-Or算法

4. KMP算法

还有其他更好的高速字符串匹配算法可以尝试吗？

编辑：有另一个类似的主题，其中也有很好的参考资料。

- sashank

---

可以看看这里：http://www-igm.univ-mlv.fr/~lecroq/string/index.html - Nabb

非常棒的收藏！非常感谢Nabb！ - sashank

Answer 1

据我所知，双向字符串匹配是最好的通用字符串匹配算法。它具有线性最坏情况复杂度，使用恒定空间，并且不会过多地回溯。其背后的理论非常出色。

如果您知道您的用户不是笨蛋，则针对您的架构进行优化的朴素字符串匹配算法将在短“针”上获胜，而Boyer-Moore变体将开始为长“针”执行次线性操作。但是，朴素字符串匹配具有二次最坏情况，而Boyer-Moore可能需要检查输入中的所有字符。处理不匹配所需的额外表格实际上比双向字符串匹配带来了惊人的严重惩罚。

- tmyklebu

Answer 2

你也可以尝试以下算法：

• Z算法：在某些方面比KMP更加简洁
• Aho-Corasick算法：基于Trie树，最初用于fgrep
• Rabin-Karp算法：基于哈希

- Thomas Ahle

Answer 3

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

    }
}

- Deepak Kumar

---

欢迎。您可以通过解释一些关于这个算法的内容来使答案更好，也许是与问题中提到的其他算法进行比较？ - Mark Chorley