黑马程序员技术交流社区
标题: java经典算法之字符串核对（String Match） [打印本页]
作者: 王海彬 时间: 2015-9-17 22:18
标题: java经典算法之字符串核对（String Match）
问题说明：
现在的一些高级程序语言对于字符串的处理支持越来越大，不过字符串搜寻本身仍是值得探讨的课题，在这里以Boyer Moore法来说明如何进行字符串说明，这个方法速度快且容易理解。
算法代码：
1.
2. import java.io.BufferedReader;
3. import java.io.IOException;
4. import java.io.InputStreamReader;
5.
6. public class StringMatch {
7. private int[] skip;
8. private int p;
9. private String str;
10. private String key;
11.
12. public StringMatch(String key) {
13. skip = new int[256];
14. this.key = key;
15.
16. for(int k = 0; k <= 255; k++)
17. skip[k] =key.length();
18. for(int k = 0; k < key.length() -1; k++)
19. skip[key.charAt(k)] =key.length() - k - 1;
20. }
21.
22. public void search(String str) {
23. this.str = str;
24. p = search(key.length()-1, str,key);
25. }
26.
27. private int search(int p, String input, String key) {
28. while(p < input.length()) {
29. String tmp =input.substring(
30. p-key.length()+1, p+1);
31.
32. if(tmp.equals(key)) // 比较两个字符串是否相同
33. returnp-key.length()+1;
34. p +=skip[input.charAt(p)];
35. }
36.
37. return -1;
38. }
39.
40. public boolean hasNext() {
41. return (p != -1);
42. }
43.
44. public String next() {
45. String tmp = str.substring(p);
46. p = search(p+key.length()+1, str,key);
47. return tmp;
48. }
49.
50. public static void main(String[] args)
51. throws IOException {
52. BufferedReader bufReader =
53. new BufferedReader(
54. new InputStreamReader(System.in));
55.
56. System.out.print("请输入字符串：");
57. String str = bufReader.readLine();
58. System.out.print("请输入搜寻关键字：");
59. String key = bufReader.readLine();
60.
61. StringMatch strMatch = new StringMatch(key);
62. strMatch.search(str);
63.
64. while(strMatch.hasNext()) {
65. System.out.println(strMatch.next());
66. }
67. }
68. }
| 欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) |
黑马程序员IT技术论坛 X3.2 |