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

2019-12-23 15:28junjie JAVA教程

这篇文章主要介绍了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; 

									  } 

									}