字符串匹配查找算法中，最著名的两个是KMP算法（Knuth-Morris-Pratt)和BM算法（Boyer-Moore)。两个算法在最坏情况下均具有线性的查找时间。但是在实用上，KMP算法并不比最简单的C库函数strstr()快多少，而BM算法则往往比KMP算法快上3－5倍(未亲身实践)。但是BM算法还不是最快的算法，这里介绍一种比BM算法更快一些的查找算法Sunday算法。
Sunday算法的思想和BM算法中的坏字符思想非常类似。差别只是在于Sunday算法在匹配失败之后，是取目标串中当前和Pattern字符串对应的部分后面一个位置的字符来做坏字符匹配。当发现匹配失败的时候就判断母串中当前偏移量+Pattern字符串长度+1处(假设为K位置)的字符在Pattern字符串中是否存在。如果存在，则将该位置和Pattern字符串中的该字符对齐，再从头开始匹配；如果不存在，就将Pattern字符串向后移动，和母串k+1处的字符对齐，再进行匹配。重复上面的操作直到找到，或母串被找完结束。动手写了个小例子来实现以下这个算法。
在代码中，实现了两种字符串匹配算法，一种是Sunday方式，一种是普通的每次移动一位的方式，二者的效率对比在main函数中有，都是纳秒级别。算法的详细步骤，在代码中已经添加了相应的注释。关于BM算法，下次空了再一起对照着分析。
复制代码 代码如下:
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
/**
* @author Scott
* @date 2013年12月28日
* @description
*/
public class SundySearch {
String text = null;
String pattern = null;
int currentPos = 0;
/**
* 匹配后的子串第一个字符位置列表
*/
List<Integer> matchedPosList = new LinkedList<Integer>();
/**
* 匹配字符的Map,记录改匹配字符串有哪些char并且每个char最后出现的位移
*/
Map<Character, Integer> map = new HashMap<Character, Integer>();
public SundySearch(String text, String pattern) {
this.text = text;
this.pattern = pattern;
this.initMap();
};
/**
* Sunday匹配时，用来存储Pattern中每个字符最后一次出现的位置，从左到右的顺序
*/
private void initMap() {
for (int i = 0; i < pattern.length(); i++) {
this.map.put(pattern.charAt(i), i);
}
}
/**
* 普通的字符串递归匹配，匹配失败就前进一位
*/
public List<Integer> normalMatch() {
//匹配失败，继续往下走
if (!matchFromSpecialPos(currentPos)) {
currentPos += 1;
if ((text.length() - currentPos) < pattern.length()) {
return matchedPosList;
}
normalMatch();
} else {
//匹配成功，记录位置
matchedPosList.add(currentPos);
currentPos += 1;
normalMatch();
}
return matchedPosList;
}
/**
* Sunday匹配，假定Text中的K字符的位置为：当前偏移量+Pattern字符串长度+1
*/
public List<Integer> sundayMatch() {
// 如果没有匹配成功
if (!matchFromSpecialPos(currentPos)) {
// 如果Text中K字符没有在Pattern字符串中出现，则跳过整个Pattern字符串长度
if ((currentPos + pattern.length() + 1) < text.length()
&& !map.containsKey(text.charAt(currentPos + pattern.length() + 1))) {
currentPos += pattern.length();
}else {
// 如果Text中K字符在Pattern字符串中出现，则将Text中K字符的位置和Pattern字符串中的最后一次出现K字符的位置对齐
if ((currentPos + pattern.length() + 1) > text.length()) {
currentPos += 1;
} else {
currentPos += pattern.length() - (Integer) map.get(text.charAt(currentPos + pattern.length()));
}
}
// 匹配完成，返回全部匹配成功的初始位移
if ((text.length() - currentPos) < pattern.length()) {
return matchedPosList;
}
sundayMatch();
}else {
// 匹配成功前进一位然后再次匹配
matchedPosList.add(currentPos);
currentPos += 1;
sundayMatch();
}
return matchedPosList;
}
/**
* 检查从Text的指定偏移量开始的子串是否和Pattern匹配
*/
public boolean matchFromSpecialPos(int pos) {
if ((text.length()-pos) < pattern.length()) {
return false;
}
for (int i = 0; i < pattern.length(); i++) {
if (text.charAt(pos + i) == pattern.charAt(i)) {
if (i == (pattern.length()-1)) {
return true;
}
continue;
} else {
break;
}
}
return false;
}
public static void main(String[] args) {
SundySearch sundySearch = new SundySearch("hello 啊啊 阿道夫 adfsadfklf adf234masdfsdfdsfdsfdsffwerwrewrerwerwersdf2666sdflsdfk", "adf");
long begin = System.nanoTime();
System.out.println("NormalMatch:" + sundySearch.normalMatch());
System.out.println("NormalMatch:" + (System.nanoTime() - begin));
begin = System.nanoTime();
System.out.println("SundayMatch:" + sundySearch.sundayMatch());
System.out.println("SundayMatch:" + (System.nanoTime() - begin));
}
}
【java实现sunday算法示例分享】相关文章：