string - 高速字符串匹配算法

Question

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

1. Gonzalo Navarro 和 Mathieu Raffinot 的反向非确定性 DAWG（有向无环词图）匹配算法。请参阅“后缀自动机的位并行方法：快速扩展字符串匹配”

2. Horspool 改进版的 Boyer-Moore 字符串搜索算法。请参阅“字符串中的实用快速搜索”

3. 不匹配的 Shift-Or 算法

4. KMP

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

编辑：在类似的行中有另一个线程，它也有很好的参考

Answer 1

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

如果您知道您的用户不是混蛋，那么为您的架构优化的天真字符串匹配将赢得短“针”，而 Boyer-Moore 变体将开始真正为长“针”做亚线性的事情。然而，朴素字符串匹配具有二次最坏情况，并且可以使用 Boyer-Moore 来检查输入中的所有字符。处理不匹配所需的额外表实际上比双向字符串匹配带来了令人惊讶的严重惩罚。

Answer 2

你也可以试试

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

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

    }
}