Java搜索字符串（kmp）

我想搜索一个字符串（可以说a）出现在字符串b中的次数。我想过实现Knuth-Morris-Pratt算法，但我更喜欢内置的java函数。有没有这样的功能？我希望函数尽可能地使用最低复杂度，因为我多次使用它。Java搜索字符串（kmp）

来源

2012-04-14 The GiG

你能更具体吗？您是否在较大的文本内搜索小型查询？ – Tudor 2012-04-14 18:11:10

KMP算法是而不是标准Java库的一部分，但很容易找到在线实现，如this one。

来源

2012-04-14 18:11:58

这是我做过的一个很老的项目的一部分。可能对启发有好处，但不确定它是否是最快的方式。

Basiclly Basiclly你使用Automaton函数来创建一个状态机表。然后，你使用数学函数来检查出现！

自动机帕拉姆：模式是你要找的图案和字母是该模式的所有caracters（例如：模式 - aabba，阿尔法 - AB）

我对法国意见appologies！

public Automaton(String pattern, char[] alpha){ 

    //declaration et initialisation 
    _alpha = alpha; 
    _pattern = pattern; 
    int m = pattern.length(); 
    String Pqa = ""; 
    String Pk = ""; 

    //Initialisation du Map 
    for(int map = 0; map < alpha.length ; map++){ 
     alphaMapc.put(alpha[map],alpha[map]); 
     alphaMapNum.put(alpha[map],map); 
    } 

    tableau = new int[pattern.length()+1][alpha.length]; 

    // Algo d'apres le pseduo code et les notes 
    for(int q=0 ; q <= m ; q++){    
     for(int j =0 ; j < alpha.length ; j++ ){ 
      Pqa = pattern.substring(0,q); 
      Pqa += alpha[j]; 
      int k = Math.min(m+1, q+2); 

      //Do while qui test Pq avec toutes le fins possibles 
      do{ 
       k = k-1; 
       Pk = pattern.substring(0, k); 

      }while(k >0 && !(Pqa.endsWith(Pk))); 

      tableau[q][j] = k; 
      System.out.print(k + " "); // TEST OUTPUT 
     } 
     System.out.println(); // TEST OUTPUT 
    } 



} 

public int match(String string) { 

    //Initialisation de letat et du compte 
    int etat = 0; 
    int compte = 0; 

    for(int s = 0; s < string.length() ; s++){   
     char t = string.charAt(s);  

     //Acces en O(1) 
     if(t == alphaMapc.get(t)) etat = tableau[etat][alphaMapNum.get(t)]; 

     //Si on atteint un etat final, on recommence a l'entree de la machine et on increment le compteur 
     if(etat == 15){ 
      etat = 0; 
      compte++; 
     } 
    } 

    //Test 
    System.out.println("Compte: " + compte); 
    return compte; 
}

希望它有帮助！

问候， Erwald

来源

2012-04-14 18:19:41 Erwald

在Java中，你可以简单地使用String.indexOf()方法。

它不使用KMP算法。对于短字符串来说，它已经足够好了，但是如果你需要性能，并且打算使用大字符串，那么这不是一个好选择。

但是，如果你想有一个简单的解决方案，那就是：

int n = 0, i = 0; 
while (i < str.length() 
     && (i = str.indexOf("al", i)) != -1) { 
    ++n; 
    ++i; 
} 
System.out.println("n: " + n);

它计算的子字符串的所有出现。

来源

2012-04-14 18:21:51 dash1e

Java搜索字符串（kmp）

回答

相关问题