/** 
 * 樸素字符串算法通過兩層循環(huán)來尋找子串， 
 * 好像是一個(gè)包含模式的“模板”沿待查文本滑動(dòng)。 
 * 算法的思想是：從主串S的第pos個(gè)字符起與模式串進(jìn)行比較， 
 * 匹配不成功時(shí)，從主串S的第pos+1個(gè)字符重新與模式串進(jìn)行比較。 
 * 如果主串S的長度是n，模式串長度是 m，那么Brute-Force的時(shí)間復(fù)雜度是o(m*n)。 
 * 最壞情況出現(xiàn)在模式串的子串頻繁出現(xiàn)在主串S中。 
 * 雖然它的時(shí)間復(fù)雜度為o(m*n)，但在一般情況下匹配時(shí)間為o(m+n)， 
 * 因此在實(shí)際中它被大量使用。 
 * 該方法的優(yōu)點(diǎn)是：算法簡單明朗，便于實(shí)現(xiàn)記憶。 
 * 該方法的缺點(diǎn)是：進(jìn)行了回溯，效率不高，而這些回溯都是沒有必要的。 
 * 下面是該算法的Java代碼，找到子串的話，返回子串在父串中第一次出現(xiàn)的位置， 
 * 找不到的話返回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指向主串下一個(gè)位置 
      for(int j=0; j<patternLength; j++) { 
        if(waitForMatch.charAt(k) != pattern.charAt(j)) { 
          break; 
        }else { 
          k++;// 指向主串下一個(gè)位置 
          if(j == patternLength-1) { 
            return i; 
          } 
        }           
      } 
    } 
    // 匹配不成功，返回0 
    return 0; 
  } 
}