软件编程
位置：首页>> 软件编程>> java编程>> Java数据结构及算法实例：朴素字符匹配 Brute Force

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

作者：junjie　　发布时间：2022-01-10 15:03:40　

标签：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;
 }
}
0
投稿

猜你喜欢

手机版 软件编程 asp之家 www.aspxhome.com