对于经典模式匹配算法的一些改动
从一个很长的字符串（或者数组）中，查找某个子串（模式串）是否存在，在算法上被称为是“模式匹配”。
模式匹配的经典算法包括KMP算法、BM算法等等。以下简要回顾这些经典算法的思想，并说明我对此的改进想法。
KMP算法
首先对模式串进行处理，获得当某个字符位置失配的时候，比较位置的指针应该指向的下一个位置的数组。举例如下：
/** * @version 1.0 * @author Regular * @date 2009-06-11 */package cn.sh.huang;import java.io.File;import java.io.FileInputStream;import java.nio.charset.Charset;public class StringCmp{ /** * Entrance method * * @param args */ public static void main(String[] args) throws Exception { String fileName = "C:\\Program Files\\Java\\jdk1.6.0_13\\LICENSE"; String pattern = "enef"; File file = new File(fileName); int fileLen = (int) file.length(); FileInputStream fis = new FileInputStream(file); byte[] buffer = new byte[fileLen]; fis.read(buffer); int i = indexOfData(buffer, 0, pattern); System.out.println(i); } private static int indexOfData(byte[] buffer, int index, String s) { byte[] pattern = s.getBytes(Charset.forName("US-ASCII")); int[] fast_shift = new int[256]; // 模式串尾字符比较结果的移动 for (int i = 0; i < 256; i++) { fast_shift[i] = pattern.length; } for (int i = pattern.length - 1, j = 0; i >= 0; i--, j++) { int x = 0xFF & pattern[i]; if (fast_shift[x] > j) { fast_shift[x] = j; } } int[] slow_shift = new int[pattern.length]; // 改KMP算法的移动 getNextStep(pattern, slow_shift); int cursor = 0; outterLoop: while (index + pattern.length <= buffer.length) { // 首先检查index + pattern.length - 1位置的字符，决定快速移动距离 int x = 0xFF & buffer[index + pattern.length - 1]; int shift = fast_shift[x]; if (shift > 0) { index += shift; cursor = 0; continue; } // 若尾字符一致，使用改KMP算法决定慢速移动距离 while (cursor < pattern.length - 1) { if (pattern[cursor] != buffer[index + cursor]) { index += slow_shift[cursor]; cursor = cursor - slow_shift[cursor]; if (cursor < 0) { cursor = 0; } continue outterLoop; } cursor++; } return index; } return -1; } /** * <pre> * idx = max(0, n - step) * a b a b a c a b a b a d step idx * X a b a b a c a b a b a d 1 0 * a X b a b a c a b a b a d 1 0 * a b X a b a b a c a b a b a d 3 0 * a b a X b a b a c a b a b a d 3 0 * a b a b X a b a b a c a b a b a d 5 0 * a b a b a X a c a b a b a d 2 3 * a b a b a c X a b a b a c a b a b a d 7 0 * a b a b a c a X b a b a c a b a b a d 7 0 * a b a b a c a b X a b a b a c a b a b a d 9 0 * a b a b a c a b a X b a b a c a b a b a d 9 0 * a b a b a c a b a b X a b a b a c a b a b a d 11 0 * a b a b a c a b a b a X a b a b a d 6 5 * </pre> * @param pattern * @param next */ private static void getNextStep(byte[] pattern, int[] next) { for (int i = 0; i < pattern.length; i++) { next[i] = i + 1; } // 卷积 for (int delta = 1; delta < pattern.length; delta++) { int i = 0; int j = i + delta; while (pattern.length > j && pattern[i] == pattern[j]) { i++; j++; } if (pattern.length > j) { if (next[j] > delta) { next[j] = delta; } } } }}总体看来，还是BM算法更好一些，其效率比KMP算法更高。
我这里虽然借用了BM的坏字符思想并改进了KMP的步进值计算，但由于逐字符比较始终是从头开始，而不像BM算法是从尾部开始，所以小挪移的潜力没有BM的那么大。
后续设想
若模式串相对较长的话，可以在模式串中找几个稀疏分布的点，比较的时候，首先比较这几个点的字符是否与源串相同，如果不同就没必要逐个字符比较了，肯定不一致，可以往后挪了。 1 楼 lin_style 2009-06-12 重温，兼收藏。 2 楼 iamsk 2009-06-16 收藏，有空定会细看的。