|
问题说明： 现在的一些高级程序语言对于字符串的处理支持越来越大，不过字符串搜寻本身仍是值得探讨的课题，在这里以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. }
| 
收藏
淘帖
踩
