我想搜索一个字符串(可以说a)出现在字符串b中的次数。 我想过实现Knuth-Morris-Pratt算法,但我更喜欢内置的java函数。有没有这样的功能?我希望函数尽可能地使用最低复杂度,因为我多次使用它。Java搜索字符串(kmp)
1
A
回答
2
KMP算法是而不是标准Java库的一部分,但很容易找到在线实现,如this one。
0
这是我做过的一个很老的项目的一部分。可能对启发有好处,但不确定它是否是最快的方式。
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
0
在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);
它计算的子字符串的所有出现。
相关问题
- 1. KMP字符串搜索算法?
- 2. Java的搜索字符串
- 3. 搜索字符串
- 4. 字符串搜索
- 5. 搜索字符串
- 6. 搜索字符串
- 7. 字符串搜索
- 8. 搜索字符串
- 9. 搜索字符串
- 10. Java中的字符串搜索算法
- 11. Java搜索2D字符串数组
- 12. 在Java中搜索字符串数组?
- 13. Java中的Wild Card搜索字符串
- 14. Java通过字符串搜索
- 15. 最佳搜索字符串中的子字符串java
- 16. sed命令来搜索字符串和搜索的字符串
- 17. VBA搜索字符串,字符串
- 18. 搜索字符串内的字符串
- 19. 搜索字符串中的字符串
- 20. 搜索字符串文字
- 21. vb.net搜索搜索字符串
- 22. sql搜索csv字符串
- 23. 搜索在HTML字符串
- 24. 字符串搜索数组
- 25. 搜索Json字符串
- 26. 搜索LPSTR字符串
- 27. 从线搜索字符串
- 28. Python的搜索字符串
- 29. 在字符串中搜索'$'
- 30. 内容搜索字符串
你能更具体吗?您是否在较大的文本内搜索小型查询? – Tudor 2012-04-14 18:11:10