Sunday算法详解及Java实现.doc

Sunday算法详解及Java实现 背景Sunday算法是Daniel M.Sunday于1990年提出的字符串模式匹配。其效率在匹配随机的字符串时比其他匹配算法还要更快。Sunday算法的实现可比KMP，BM的实现容易太多。Sunday算法由Daniel M.Sunday在1990年提出，它的思想跟BM算法很相似： ?只不过Sunday算法是从前往后匹配，在匹配失败时关注的是文本串中参加匹配的最末位字符的下一位字符。 如果该字符没有在模式串中出现则直接跳过，即移动位数 = 匹配串长度 + 1； 否则，其移动位数?= 模式串中最右端的该字符到末尾的距离+1。分析 假设我们有如下字符串： = LESSONS TEARNED IN SOFTWARE TE; T = SOFTWARE; Sunday算法的大致原理是： 先从左到右逐个字符比较，以我们的字符串为例： 开始的时候，我们让i = 0, 指向的第一个字符; j = 0 指向的第一个字符，分别为L和S，不等；这个时候，Sunday算法要求，找到位于字串中位于字符串后面的第一个字符，即下图中 m所指向的字符T，在模式字符串中从后向前查找是否存在T 可以看到下图中k指向的字符与m指向的字符相等 移动模式串5位，这时就将相等的字符对齐，让j再次指向的头一个字符，相应地，将i指向对应的字符N。 再次比较[i]和[j]，不等，这时再次寻找主串中在模式串后面的那个字符 k指向的模式串与m指向的主串字符相等，因此再次移动 这时，主串i对应的字符是，j对应的子串字符也是S，i++, j++ 现在再次不等， m指向字符 由于m指向字符D字符D再次比较[i]和[j]，不等，这时再次寻找主串中在模式串后面的那个字符 k指向的模式串与m指向的主串字符相等，因此再次移动 依次比较S[i]和[j]，直到比较模式串T最后一个字符“E”，完全一致，查找成功。 完整代码 public class SundayTest { /** * 主函数 * * @param args 参数数组 */ public static void main(String[] args) { // 定义原始数据 String text = LESSONS TEARNED IN SOFTWARE TE; String pattern = SOFTWARE; System.out.println(S:\t + text); System.out.println(T:\t + pattern); // 测试下一序号数组 int[] next = next(pattern.toCharArray()); System.out.println(下一序号数组:); for (int i = 0; i next.length; i++) { if (next[i] != -1) { System.out.println(next[ + (char) i + ]: + next[i]); } } // 测试Sunday查找算法 System.out.println(Sunday:\t + sunday(text.toCharArray(), pattern.toCharArray())); System.out.println(String:\t + text.indexOf(pattern)); } /** * 下一序号数组 * * @param T 模式字符数组 * @return 下一序号表 */ public static int[] next(char[] T) { // 初始序号数组 int[] = new int[65536]; // 填充坏字符序号 Arrays.fill(, -1); // 填充好字符序号(以最后位置为准) for (int j = 0; j T.length; j++) { [T[j]] = j; } // 返回序号数组 return ; } /** * Sunday查找 * * @param S 正文字符数组 * @param T 模式字符数组 * @return 匹配位置 */ public static int sunday(char[] S, char[] T) { // 检查输入参数有效 if (S == null || T == null || S.length == 0 || T.length == 0 || T.length S.length) { return -1; }