Java数据结构及算法实例:朴素字符匹配 Brute Force

时间:2022-08-22 13:20:26
?
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;
  }
}