Algoritmos de coincidencia de cadenas de alta velocidad

Question

Básicamente estoy comparando algunos algoritmos de coincidencia de cadenas de alta velocidad, me encontré con algunos.

1. hacia atrás DAWG no determinista (Dirigida palabra gráfico acíclico) algoritmo Matching por Gonzalo Navarro y Mathieu Raffinot. Ver "Un enfoque bits en paralelo a sufijo Autómatas: Rápido extendido Cadena Matching" versión mejorada

2. de Horspool del algoritmo de búsqueda de Boyer-Moore cadena . Consulte "Búsqueda rápida práctica en cadenas"

3. Shift-O algoritmo con desajustes

4. KMP

¿Hay otros algoritmos mejor cadena de alta velocidad de juego que pueda intentar?

Editar: Hay otro thread en líneas similares, que tiene buenas referencias demasiado

Answer 1

También puede tratar

• Z Algorithm: En algunos aspectos incluso más limpio que KMP
• Aho Corasick: basada Trie y originalmente utilizado para fgrep
• Rabin Karp: basado en Hash

Answer 2

La coincidencia de cadenas bidireccionales es, que yo sepa, el mejor algoritmo de propósito general para la coincidencia de cadenas. Tiene complejidad lineal en el peor de los casos, utiliza espacio constante y no retrocede demasiado más de lo necesario. Y la teoría detrás de esto es muy agradable.

Si sabe que sus usuarios no son idiotas, la coincidencia ingeniosa de cuerdas optimizada para su arquitectura ganará por "agujas" cortas, mientras que una variante de Boyer-Moore comenzará a hacer realmente lo sublineal para largas "agujas". Sin embargo, la coincidencia de cuerdas ingenua tiene un peor caso cuadrático y se puede hacer que Boyer-Moore examine todos los caracteres de la entrada. Las tablas adicionales necesarias para manejar desajustes en realidad tienen una penalización sorprendentemente severa sobre la coincidencia de cadenas bidireccionales.

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

    } 
}