0001 /* 0002 * 串模式匹配:KMP算法 0003 * 若返回位置i > length(T) - length(P),则说明失配 0004 * 否则,i为匹配位置 0005 */ 0006 import dsa.*; 0007 import java.io.*; 0008 0009 public class PM_KMP { 0010 ////////////////////////////////////////////////////////////////////////// 0011 // T: 0 1 . . . i i+1 . . . i+k . . n-1 0012 // --------------------|-------------------|------------ 0013 // P: j j+1 . . . j+k . . 0014 // |-------------------| 0015 ////////////////////////////////////////////////////////////////////////// 0016 public static int PM(String T, String P) {//KMP算法 0017 int[] next = BuildNextImproved(P);//构造next[]表 0018 int i = 0;//文本串指针 0019 int j = 0;//模式串指针 0020 while(j < P.length() && i < T.length()) { //自左向右逐个比较字符 0021 ShowProgress(T, P, i - j, j); ShowNextTable(next, i - j, P.length()); System.out.println(); 0022 if (0 > j || T.charAt(i) == P.charAt(j)) { //若匹配,或P已移出最左侧(提问:这两个条件能否交换次序?) 0023 i++; j++;//则转到下一对字符 0024 } else//否则 0025 j = next[j];//模式串右移(注意:文本串不用回退) 0026 }//while 0027 return(i - j); 0028 } 0029 0030 protected static int[] BuildNext(String P) {//建立模式串P的next[]表 0031 int[] next = new int[P.length()];//next[]表 0032 int j = 0;//“主”串指针 0033 int t = next[0] = -1;//“模式”串指针 0034 while (j < P.length() - 1) 0035 if (0 > t || P.charAt(j) == P.charAt(t)) {//匹配 0036 j++; t++; 0037 next[j] = t;//此句可以改进... 0038 } else//失配 0039 t = next[t]; 0040 for (j = 0; j < P.length(); j++) System.out.print("\t" + P.charAt(j)); System.out.print("\n"); 0041 ShowNextTable(next, 0, P.length()); 0042 return(next); 0043 } 0044 0045 protected static int[] BuildNextImproved(String P) {//建立模式串P的next[]表(改进版本) 0046 int[] next = new int[P.length()];;//next[]表 0047 int j = 0;//“主”串指针 0048 int t = next[0] = -1;//“模式”串指针 0049 while (j < P.length() - 1) 0050 if (0 > t || P.charAt(j) == P.charAt(t)) {//匹配 0051 j++; t++; 0052 next[j] = (P.charAt(j) != P.charAt(t)) ? t : next[t];//注意此句与未改进之前的区别 0053 } else//失配 0054 t = next[t]; 0055 for (j = 0; j < P.length(); j++) System.out.print("\t" + P.charAt(j)); System.out.print("\n"); 0056 ShowNextTable(next, 0, P.length()); 0057 return(next); 0058 } 0059 0060 0061 protected static void ShowNextTable(//显示next[]表,供演示分析 0062 int[] N, 0063 int offset, 0064 int length) { 0065 int i; 0066 for (i = 0; i < offset; i++) System.out.print("\t"); 0067 for (i = 0; i < length; i++) System.out.print("\t" + N[i]); System.out.print("\n\n"); 0068 } 0069 0070 protected static void ShowProgress(//动态显示匹配进展 0071 String T,//文本串 0072 String P,//模式串 0073 int i,//模式串相对于文本串的起始位置 0074 int j) { //模式串的当前字符 0075 int t; 0076 System.out.println("-------------------------------------------"); 0077 for (t = 0; t < T.length(); t++) System.out.print("\t" + T.charAt(t)); System.out.print("\n"); 0078 if (0 <= i + j) { 0079 for (t = 0; t < i + j; t++) System.out.print("\t"); 0080 System.out.print("\t|"); 0081 } 0082 System.out.println(); 0083 for (t = 0; t < i; t++) System.out.print("\t"); 0084 for (t = 0; t < P.length(); t++) System.out.print("\t" + P.charAt(t)); System.out.print("\n"); 0085 System.out.println(); 0086 } 0087 }