程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> JAVA編程 >> 關於JAVA >> Java數據構造及算法實例:樸實字符婚配 Brute Force

Java數據構造及算法實例:樸實字符婚配 Brute Force

編輯:關於JAVA

Java數據構造及算法實例:樸實字符婚配 Brute Force。本站提示廣大學習愛好者:(Java數據構造及算法實例:樸實字符婚配 Brute Force)文章只能為提供參考,不一定能成為您想要的結果。以下是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; 
  } 
} 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved