字符串模式匹配算法包括三种:蛮力方式，BM模式匹配，KMP模式匹配
蛮力方式容易理解，比较方向从左往右逐个比较，最坏时间复杂度可达O(m·n)(m为 模式字符串长度，n为源字符串长度)，最好时间复杂度O(m).
BM模式匹配采用了两个启发式原则:坏字符和好后缀原则，从而避免一些不必要的比较
最坏时间复杂度为O(m·n),最好时间复杂度为O(n/m).
附BM模式匹配代码
/** * BoyerBoomer算法查找 * @param src 源字符串 * @param dst 模式字符串 * @return int 匹配成功返回1,失败返回0 */ public static int BoyerBoomerMatchPractice(String src,String dst) { int srclength=src.length(); int dstlength=dst.length(); int s=dstlength-1,d=dstlength-1; int srcs=dst.length()-1; while(srcs<=srclength-1) {//双循环，当循环到源字符串末尾时结束循环 while(d>=0) {//根据模式字符串进行循环判定 if(src.charAt(s)==dst.charAt(d)) { s-=1;//若相等从右向左逐步移动一位 d-=1; } else { int temp=last(dst,src,d,s);//判定移动函数，分为坏字符和最好后缀两种情况 srcs+=temp; System.out.println("fdsfsdf " +src.substring(0,srcs)+" "+temp+" srcs"+srcs); s=srcs; d=dstlength-1; break; } } System.out.println(" "+d); if(d==-1) return 1; } return 0; } /** * 获得移动的步数 * @param dst 模式字符串 * @param src 源字符串 * @param d 模式字符串已匹配的计数 * @param ssss 源字符串中不匹配的计数 * @return 移动的步数 */ public static int last(String dst,String src,int d,int ssss) { //首先判定是否为坏字符 if(d==dst.length()-1) {//是 char lastchar=src.charAt(ssss); System.out.println("lastchar"+lastchar+" "+ssss); //判定字符是否在模式字符串当中存在 int i; for(i=0;i<=dst.length()-1;i++) if(lastchar==dst.charAt(i)) break; if(i==dst.length()) { System.out.println(1+"坏字符"); return 1; } else { System.out.println((d-i)+"坏字符else"+"d "+d+ "i "+i); return d-i; } } else {//否，找好后缀 String goodend=dst.substring(d+1,dst.length());//获得好后缀 return isexitst(dst,goodend); } } /** * 当模式字符串当中不存在好后缀时，获得移动的步数 * @param dst 模式字符串 * @param goodend 好后缀 * @return 移动的步数 */ public static int isexitst(String dst,String goodend){ int s=dst.length()-2;//跳过最后一个字符 int ss=dst.length()-2; int d=goodend.length()-1; while(s>=d) {//采用蛮力方式来判断模式字符串当中是否存在好后缀 while(d>=0) { if(dst.charAt(s)==goodend.charAt(d)) { s-=1; d-=1; } else { ss-=1; s=ss; d=goodend.length()-1; break; } } if(d==-1) { System.out.println("存在好后缀 "+(dst.length()-(s+1+goodend.length()))); return dst.length()-(s+1+goodend.length()); } }//不存在好后缀 //就寻找最好的最前缀 int dtime=d; int ds=0;//位置 String sgoodend=goodend; while(dtime>=0) {//按照后缀从前往后逐步减一进行判断 if(dst.startsWith(sgoodend)){ System.out.println("最好的最前缀 "+(dst.length()-sgoodend.length())); return dst.length()-sgoodend.length();} else { ds+=1; sgoodend=goodend.substring(ds,goodend.length()); } dtime-=1; } return 1; }
