public class HelloWorld {
public static void main(String[] args) {
// char[] a = { '记','录','模','式','串','中','每','个','字','符','最','后','出','现','的','位','置' };
// char[] b = { '每','个','字'};
char[] a = { 'I', 'L', 'o', 'v', 'e', 'C', 'o', 'd', 'e' };
char[] b = { 'd', 'e'};
System.out.println("asccii "+ (int)'式');
System.out.println("char [] 长度" +a.length);
int index = BM(a,a.length,b,b.length);
System.out.println("查找到的位置在第 "+ index+" 个");
}
private static final int SIZE = 256; // 全局变量或成员变量
// a,b表示主串和模式串；n，m表示主串和模式串的长度。
public static int BM(char[] a,int n,char[] b,int m) {
int[] bc = new int[SIZE]; // 记录模式串中每个字符最后出现的位置
generateBC(b, m, bc); // 构建坏字符哈希表
int[] suffix = new int[m];
boolean[] prefix = new boolean[m];
generateGS(b, m, suffix, prefix);
int i = 0; // j表示主串与模式串匹配的第一个字符
while (i <= n - m) {
int j;
for (j = m - 1; j >= 0; --j) { // 模式串从后往前匹配
if (a[i+j] != b[j]) break; // 坏字符对应模式串中的下标是j
}
if (j < 0) {
return i; // 匹配成功，返回主串与模式串第一个匹配的字符的位置
}
int x = j - bc[(int)a[i+j]];
int y = 0;
if (j < m-1) { // 如果有好后缀的话
y = moveByGS(j, m, suffix, prefix);
}
i = i + Math.max(x, y);
}
return -1;
}
//散列表,数组的下标对应字符的ASCII码值,数组中存储这个字符在模式串中出现的位置
//注:如果模式串中出现相同的字符那就记录后面的
/* 模式串 a b d a
ASSCII表 0 1 2 3 （模式串里出现了两个“a”,只会记录一个位置,后面出现的刷新前面的位置）
a 97 bc: -1 -1 ... 3 1 -1 2 .... -1
b 98 0 1 ... 97 98 99 100 .... 255
c 99
d 100
.....*/
//这里的hash算法太简单了,只适合用来匹配字母，如果需要匹配中文那就需要改进hash算法
public static void generateBC(char[] b, int m, int[] bc) {
for (int i = 0; i < SIZE; ++i) {
bc[i] = -1; // 初始化bc
}
for (int i = 0; i < m; ++i) { // i递增,巧妙的将出现相同的字符时,后面的将前面的数值覆盖
int ascii = (int)b[i]; // 计算b[i]的ASCII值
bc[ascii] = i;
}
}
/*suffix数组说明：表示模式串中后缀子串的长度,下标对应的数组值存储的是，在模式串中跟好后缀{u}相匹配的子串{u*}的起始下标值。
* * * * * * * * * c a b * * * * *
------(这是{u})
模式串 c a b c a b
------(这是{u*})
↓ ↓ ↓
起始下标值 0 1 2
后缀子串 长度 suffix
b 1 suffix[1] = 2
a b 2 suffix[2] = 1
c a b 3 suffix[3] = 0
b c a b 4 suffix[4] = -1 (找不到就等于-1)
a b c a b 5 suffix[5] = -1
c a b c a b 6 suffix[6] = -1
*/
// b表示模式串，m表示长度，suffix，prefix数组事先申请好了
public static void generateGS(char[] b, int m, int[] suffix, boolean[] prefix) {
for (int i = 0; i < m; ++i) { // 初始化
suffix[i] = -1;
prefix[i] = false;
}
for (int i = 0; i < m - 1; ++i) { // b[0, i]
int j = i;
int k = 0; // 公共后缀子串长度
while (j >= 0 && b[j] == b[m-1-k]) { // 与b[0, m-1]求公共后缀子串
--j;
++k;
suffix[k] = j+1; //j+1表示公共后缀子串在b[0, i]中的起始下标
}
if (j == -1) prefix[k] = true; //如果公共后缀子串也是模式串的前缀子串
}
}
// j表示坏字符对应的模式串中的字符下标; m表示模式串长度
public static int moveByGS(int j, int m, int[] suffix, boolean[] prefix) {
int k = m - 1 - j; // 好后缀长度
if (suffix[k] != -1) return j - suffix[k] +1;
for (int r = j+2; r <= m-1; ++r) {
if (prefix[m-r] == true) {
return r;
}
}
return m;
}
}