本来在看KMP算法来着，可是实在是复杂，晦涩难懂，看别人博客了解到KMP算法不仅复杂难懂，效率也不算太高，所以果断抛弃，了解到有其他更高效的算法，如BM算法，但是还有一种更高效的算法–Sunday算法。
Sunday算法的原理很简单，简单高效，这才是我们需要的。
手写描述，不喜勿喷哈哈。
package Suanfa;public class Sunday { public void sunday(String mom, String son) {// 将主串定义为mom,将匹配串定义为son // 将两个字符串转化为字符数组 char[] momChar = mom.toCharArray(); char[] sonChar = son.toCharArray(); // 分别求两个字符数组的长度 int momLen = momChar.length; int sonLen = sonChar.length; // i、j分别用来标识主串和匹配串下标 int i = 0; int j = 0; // 判断可以匹配多少个子串 int count = 0; if(momLen<sonLen){ System.out.PRintln("匹配串长度不能大于主串长度！"); } while (i <= momLen - sonLen + j) { // 判断最后一次匹配，如果无法匹配，则跳出循环 if (momChar[i] != sonChar[j]) { if (i == momLen - sonLen + j) { break; } // 返回主串比匹配串多的第一个字符在匹配串中的位置 int pos = contains(sonChar, momChar[i + sonLen - j]); // 如果下一个字符在匹配串中不存在，则直接跳到再下一个字符 if (pos == -1) { i = i + sonLen - j + 1; j = 0; } else {// 如果存在，将匹配串中的该字符与其对应，再进行匹配 i = i + sonLen - j - pos; j = 0; } } else { if (j == sonLen - 1) {// 完成一次匹配 count++; System.out.println("第"+count+"次匹配：起始下标为" + (i - j) + " 结束下标为" + i); i = i - j + 1; j = 0; } else { i++; j++; } } } } /** * 返回某一字符在某字符数组中的位置，从后往前遍历，如果不存在该字符则返回-1 * * @param ch * @param target * @return */ private int contains(char[] ch, char target) { // TODO Auto-generated method stub int len = ch.length; for (int index = len - 1; index >= 0; index--) { if (ch[index] == target) { return index; } } return -1; } public static void main(String[] args) { Sunday sun = new Sunday(); sun.sunday("wuhanligongdaxuexinxiguanli", "ig"); }}新闻热点
疑难解答
