收集一些常用的代码
 

String搜索算法

本示例出自String searching algorithm (SSA)。因为比较简单,故只给出源码不予解释。

 

Brute-force searching algorithm (BFSA)public class BruteForceSearch{

private char[] text;
private char[] pattern;
private int n;
private int m;

public void setString(String t,String p){
    this.text = t.toCharArray();
    this.pattern = p.toCharArray();
    this.n = t.length();
    this.m = p.length();
}

public int search(){
  for(int i =0; i < n-m; i++){
        int j =0;
        while(j < m && text[i+j]== pattern[j]){
              j++;
        }

        if(j == m)

           return i;

  }
    return-1;
}
}

class Test{

public static void main(String[] args){
  BruteForceSearch bfs =new BruteForceSearch();
  String text ="Lorem ipsum dolor sit amet";

  String pattern ="ipsum";

  bfs.setString(text, pattern);

  int first_occur_position = bfs.search();

  System.out.println("The text '"+ pattern +"' is first found after the "

+ first_occur_position +" position.");

  }

}


总结, BFSA 有以下特点:

  • pattern 没有被预处理.

  • 算法流程是从左到右一个字母一个字母比较.

  • 最差情况下需要 Θ(mn) 次比较.

  • 算法返回第一次出现匹配的地方.

Advantages优点

  • Simple.简单

  • Rapid approach.方法易于能快速构造

  • It is widely used.得到了广泛的应用

Disadvantages缺点

  • Too slow.查找太慢了

  • Not scalable.不具可伸缩性

2012-04-24 /
标签: 算法
 
评论
© 代码|Powered by LOFTER