0001 /* 0002 * 串模式匹配:Boyer-Moore算法 0003 * 若返回位置i > length(T) - length(P),则说明失配 0004 * 否则,i为匹配位置 0005 */ 0006 import dsa.*; 0007 import java.io.*; 0008 0009 public class PM_BM { 0010 final static int CARD_CHAR_SET = 256;//字符集规模 0011 ////////////////////////////////////////////////////////////////////////// 0012 // T: 0 1 . . . i i+1 . . . i+j . . n-1 0013 // --------------------|-------------------|------------ 0014 // P: 0 1 . . . j . . 0015 // |-------------------| 0016 ////////////////////////////////////////////////////////////////////////// 0017 public static int PM(String T, String P) { 0018 //预处理 0019 int[] BC = BuildBC(P); 0020 int[] GS = BuildGS(P); 0021 //查找匹配 0022 int i = 0;//模式串相对于文本串的起始位置(初始时与文本串左对齐) 0023 while (T.length() - P.length() >= i) { //在到达最右端前,不断右移模式串 0024 int j = P.length() - 1;//从模式串最末尾的字符开始 0025 while (P.charAt(j) == T.charAt(i + j)) //自右向左比较 0026 if (0 > --j) break; 0027 ShowProgress(T, P, i, j); System.out.print("\n"); 0028 if (0 > j)//若极大匹配后缀 == 整个模式串(说明已经完全匹配) 0029 break;//返回匹配位置 0030 else//否则 0031 i += MAX(GS[j], j - BC[T.charAt(i+j)]);//在位移量BC和GS之间选择大者,相应地移动模式串 0032 } 0033 return(i); 0034 } 0035 0036 /* 0037 * 构造Bad Charactor Shift表BC[] 0038 * 0039 * 0 BC['X'] m-1 0040 * | | | 0041 * ........................X**************************************** 0042 * |<------------ 不含字符'X' ------------>| 0043 * 0044 * 复杂度 = O(m + CARD_CHAR_SET) 0045 ******************************************************************************************/ 0046 protected static int[] BuildBC(String P) { 0047 //初始化 0048 int[] BC = new int[CARD_CHAR_SET];//BC[]表 0049 int j; 0050 for (j = 0; j < CARD_CHAR_SET; j++) 0051 BC[j] = -1;//首先假设该字符没有在P中出现 0052 //自左向右迭代:更新各字符的BC[]值 0053 for (j = 0; j < P.length(); j++) 0054 BC[P.charAt(j)] = j;//P[j]曾出现在位置j——鉴于这里的扫描次序是从左到右(即下标递增),故只要某个字符ch在P中出现过,BC[ch]就会记录下其中的最靠右的出现位置 0055 System.out.println("-- BC[] Table ---------------"); 0056 for (j = 0; j < CARD_CHAR_SET; j++) 0057 if (0 <= BC[j]) System.out.print("\t" + (char)j); 0058 System.out.println(); 0059 for (j = 0; j < CARD_CHAR_SET; j++) 0060 if (0 <= BC[j]) System.out.print("\t" + BC[j]); 0061 System.out.println("\n"); 0062 return(BC); 0063 } 0064 0065 /* 0066 * 计算P的各前缀与P的各后缀的最大匹配长度 0067 * 对于P的每一前缀P[0..j],SS[j] = max{s | P[j-s+1..j] = P[m-s..m-1]} 0068 * 0069 * 0 m-SS[j] m-1 0070 * | | | 0071 * ........................************************* 0072 * | | 0073 * <-------- SS[j] --------> 0074 * | | 0075 * ............*************************.................. 0076 * | | | | 0077 * 0 j-SS[j]+1 j m-1 0078 * 0079 * 复杂度 = O(m) 0080 ******************************************************************************************/ 0081 protected static int[] ComputeSuffixSize(String P) { 0082 int m = P.length(); 0083 int[] SS = new int[m];//Suffix Size Table 0084 int s, t;//子串P[s+1, ..., t]与后缀P[m+s-t, ..., m-1]匹配 0085 int j;//当前字符的位置 0086 // 对最后一个字符而言,与之匹配的最长后缀就是整个P串,故... 0087 SS[m-1] = m; 0088 // 从倒数第二个字符起,自右向左扫描P,依次计算出SS[]其余各项 0089 s = m - 1; t = m - 2; 0090 for (j = m - 2; j >= 0; j--) { 0091 if ((j > s) && (j - s > SS[(m-1-t)+j])) 0092 SS[j] = SS[(m-1-t)+j]; 0093 else { 0094 t = j;//与后缀匹配之子串的终点,就是当前字符 0095 s = MIN(s, j);//与后缀匹配之子串的起点 0096 while ((0 <= s) && (P.charAt(s) == P.charAt((m - 1 - t) + s))) 0097 s--;//似乎是二重循环,难道复杂度是平方量级? 0098 SS[j] = t - s; //与后缀匹配之最长子串的长度 0099 } 0100 } 0101 System.out.println("-- SS[] Table -------"); 0102 for (j = 0; j < m; j++) System.out.print("\t" + P.charAt(j)); System.out.println(); 0103 for (j = 0; j < m; j++) System.out.print("\t" + SS[j]); System.out.println("\n"); 0104 return(SS); 0105 } 0106 0107 /* 0108 * 构造Good Suffix Shift表GS[] 0109 * 复杂度 = O(m) 0110 ******************************************************************************************/ 0111 protected static int[] BuildGS(String P) { 0112 int m = P.length(); 0113 int[] SS = ComputeSuffixSize(P);//计算各字符对应的最长匹配后缀长度 0114 int[] GS = new int[m];//Good Suffix Index 0115 int j; 0116 for (j = 0; j < m; j++) GS[j] = m; 0117 /* 0118 * i < m-j-1(失配位置) 0119 * | 0120 * 0 | m-j-1 m-1 0121 * | | | | 0122 * ............A#########*********************** 0123 * | | | 0124 * | <---- Suffix Size ----><------ GS Shift ------> 0125 * | <---- SS[j] = j+1 ----><-------- m-j-1 -------> 0126 * | | | | 0127 * ***********************........................ 0128 * | | | 0129 * 0 j m-1 0130 * <--<--<--<--<--<--< 自右向扫描 <--<--<--<--<--< 0131 * 0132 ******************************************************************************************/ 0133 int i = 0; 0134 for (j = m - 1; j >= -1; j--) //提问:反过来(自左向右)扫描可以吗?为什么? 0135 if (-1 == j || j + 1 == SS[j]) //若定义SS[-1] = 0,则可统一为:if (j+1 == SS[j]) 0136 for (; i < m - j - 1; i++) //似乎是二重循环,难道复杂度是平方量级? 0137 if (GS[i] == m) 0138 GS[i] = m - j - 1; 0139 /* 0140 * m-SS[j]-1(失配位置) 0141 * | 0142 * 0 |m-SS[j] m-1 0143 * | || | 0144 * ....................A********************** 0145 * || | 0146 * |<--- Suffix Size ----><-- GS Shift -> 0147 * |<------- SS[j] ------><--- m-j-1 ---> 0148 * || | | 0149 * .....B**********************............... 0150 * | | | | 0151 * 0 j-SS[j]+1 j m-1 0152 * >-->-->-->-->--> 自左向右扫描 --->-->-->--> 0153 * 0154 ******************************************************************************************/ 0155 for (j = 0; j < m - 1; j++) //提问:反过来(自右向左)扫描可以吗?为什么? 0156 GS[m-SS[j] - 1] = m - j - 1; 0157 System.out.println("-- GS[] Table ---------------"); 0158 for (j = 0; j < m; j++) System.out.print("\t" + P.charAt(j)); System.out.println(); 0159 for (j = 0; j < m; j++) System.out.print("\t" + GS[j]); System.out.println("\n"); 0160 return(GS); 0161 } 0162 0163 protected static void ShowProgress(//动态显示匹配进展 0164 String T,//文本串 0165 String P,//模式串 0166 int i,//模式串相对于文本串的起始位置 0167 int j) { //模式串的当前字符 0168 int t; 0169 System.out.println("-------------------------------------------"); 0170 for (t = 0; t < T.length(); t++) System.out.print("\t" + T.charAt(t)); System.out.print("\n"); 0171 if (0 <= i + j) { 0172 for (t = 0; t < i + j; t++) System.out.print("\t"); 0173 System.out.print("\t|"); 0174 } 0175 System.out.println(); 0176 for (t = 0; t < i; t++) System.out.print("\t"); 0177 for (t = 0; t < P.length(); t++) System.out.print("\t" + P.charAt(t)); System.out.print("\n"); 0178 System.out.println(); 0179 } 0180 0181 protected static int MAX(int a, int b) 0182 { return (a > b) ? a : b; } 0183 0184 protected static int MIN(int a, int b) 0185 { return (a < b) ? a : b; } 0186 }