|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
|
/** * 樸素字符串算法通過兩層循環來尋找子串， * 好像是一個包含模式的“模板”沿待查文本滑動。 * 算法的思想是：從主串S的第pos個字符起與模式串進行比較， * 匹配不成功時，從主串S的第pos+1個字符重新與模式串進行比較。 * 如果主串S的長度是n，模式串長度是 m，那么Brute-Force的時間復雜度是o(m*n)。 * 最壞情況出現在模式串的子串頻繁出現在主串S中。 * 雖然它的時間復雜度為o(m*n)，但在一般情況下匹配時間為o(m+n)， * 因此在實際中它被大量使用。 * 該方法的優點是：算法簡單明朗，便于實現記憶。 * 該方法的缺點是：進行了回溯，效率不高，而這些回溯都是沒有必要的。 * 下面是該算法的Java代碼，找到子串的話，返回子串在父串中第一次出現的位置， * 找不到的話返回0. */package al; public class BruteForce { public static void main(String[] args) { String waitForMatch = "abbacbabcdabcbec"; String pattern = "abcbe"; BruteForce bruteForce = new BruteForce(); int index = bruteForce.getSubStringIndex(waitForMatch, pattern); System.out.println("Matched index is "+index); } /** * @author * @param waitForMatch 主字符串 * @param pattern 模式字符串 * @return 第一次字符串匹配成功的位置 */ public int getSubStringIndex(String waitForMatch, String pattern){ int stringLength = waitForMatch.length(); int patternLength = pattern.length(); // 從主串開始比較 for(int i=0; i<stringLength; i++) { int k = i; // k指向主串下一個位置 for(int j=0; j<patternLength; j++) { if(waitForMatch.charAt(k) != pattern.charAt(j)) { break; }else { k++;// 指向主串下一個位置 if(j == patternLength-1) { return i; } } } } // 匹配不成功，返回0 return 0; } } |
Java數據結構及算法實例：樸素字符匹配 Brute Force
2019-12-23 15:28junjie JAVA教程
這篇文章主要介紹了Java數據結構及算法實例：樸素字符匹配 Brute Force,本文直接給出實例代碼,代碼中包含詳細注釋,需要的朋友可以參考下
延伸 · 閱讀
- 2019-12-23Java數據結構及算法實例：冒泡排序 Bubble Sort
- 2019-12-23java自定義攔截器用法實例
- 2019-12-23JAVA獲得域名IP地址的方法
- 2019-12-23JAVA實現FTP斷點上傳的方法
- 2019-12-23java基于OpenGL ES實現渲染實例
- 2019-12-23java實現OpenGL ES紋理映射的方法
精彩推薦
- JAVA教程
java隨機字符補充版
今天在zuidaimai看到一個java隨機字符生成demo，正好要用，但發現不完整，重新整理一下，分享給有需要的朋友 ...
- JAVA教程
java dom4j解析xml用到的幾個方法
這篇文章主要介紹了java dom4j解析xml用到的幾個方法，有需要的朋友可以參考一下 ...
- JAVA教程
Java實現插入排序實例
這篇文章主要介紹了Java實現插入排序,實例分析了Java的插入排序原理與實現技巧,非常具有實用價值,需要的朋友可以參考下 ...
- JAVA教程
java利用mybatis攔截器統計sql執行時間示例
這篇文章主要介紹了java利用mybatis攔截器統計sql執行時間示例,該攔截器攔截mybatis的query和update操作,能統計sql執行時間 ...
- JAVA教程
Java壓縮文件ZIP實例代碼
這篇文章主要介紹了Java壓縮文件ZIP實例代碼，有需要的朋友可以參考一下 ...
- JAVA教程
java雙向循環鏈表的實現代碼
這篇文章介紹了java雙向循環鏈表的實現代碼，有需要的朋友可以參考一下 ...
- JAVA教程
Java Map的幾種循環方式總結
這篇文章主要是對Java中Map的幾種循環方式進行了詳細的總結介紹，需要的朋友可以過來參考下，希望對大家有所幫助 ...
- JAVA教程
J2EE項目代碼編寫規范分享
這篇文章主要介紹了J2EE項目代碼編寫規范分享,需要的朋友可以參考下 ...
