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

/** 
 * 朴素字符串算法通过两层循环来寻找子串， 
 * 好像是一个包含模式的“模板”沿待查文本滑动。 
 * 算法的思想是：从主串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; 
  } 
}