▶ 书中第五章部分程序，包括在加上自己补充的代码，Knuth-Morris-Pratt 无回溯匹配，Boyer - Moore 无回溯匹配，Rabin - Karp 指纹匹配
● Knuth-Morris-Pratt 无回溯匹配
package package01; import edu.princeton.cs.algs4.StdOut; public class class01
{
private final int R; // 字符集基数
private int[][] dfa; // 回溯数组
private String pat; // 模式的两种保存方式
private char[] pattern; public class01(String pat) // 分别从两种表示方式中创建回溯数组，算法仙童
{
this.R = 256;
this.pat = pat; int m = pat.length();
dfa = new int[R][m];
dfa[pat.charAt(0)][0] = 1; // 第 0 位匹配，接下来匹配第 1 位
for (int x = 0, j = 1; j < m; j++) // 跳转点初始化为 0，即某次比较后需要退回到模式的头部再开始
{
for (int c = 0; c < R; c++)
dfa[c][j] = dfa[c][x]; // 原文字母 c 与模式第 j 位比较等价于原文字母 c 与模式第 x 位比较，跳转点也相同
dfa[pat.charAt(j)][j] = j + 1; // 原文某位与模式第 j 位正确匹配，接下来应该用原文下一位与模式 j+1 位进行匹配
x = dfa[pat.charAt(j)][x]; // 设置 x 为原文某位与模式第 x 位比较后的跳转点
}
} public class01(char[] pattern, int R)
{
this.R = R;
this.pattern = new char[pattern.length];
for (int j = 0; j < pattern.length; j++)
this.pattern[j] = pattern[j]; int m = pattern.length;
dfa = new int[R][m];
dfa[pattern[0]][0] = 1;
for (int x = 0, j = 1; j < m; j++)
{
for (int c = 0; c < R; c++)
dfa[c][j] = dfa[c][x];
dfa[pattern[j]][j] = j + 1;
x = dfa[pattern[j]][x];
}
} public int search(String txt) // 利用 DFA 原理进行匹配
{
int m = pat.length(), n = txt.length(), i, j; // i 指向待匹配字符串，j 指向模式
for (i = 0, j = 0; i < n && j < m; i++) // i 不断自增，j 不断跳转
j = dfa[txt.charAt(i)][j]; // y = dfa[txt[i]][j] 表示 txt[i] 与 pattern[j] 比较后，下一步应该与 txt[i+1] 进行比较的模式的下标，
// 即下一步应该把 txt[i+1] 与 pattern[y] 进行比较
return (j == m) ? (i - m) : n; // 找到匹配则返回子字符串的索引位置，没有匹配则返回原字符串的长度
} public int search(char[] text)
{
int m = pattern.length;
int n = text.length;
int i, j;
for (i = 0, j = 0; i < n && j < m; i++)
j = dfa[text[i]][j];
return (j == m) ? (i - m) : n;
} public static void main(String[] args)
{
String pat = args[0], txt = args[1];
char[] pattern = pat.toCharArray(), text = txt.toCharArray(); // 输入存成两种格式，分别进行匹配 class01 kmp1 = new class01(pat);
int offset1 = kmp1.search(txt);
class01 kmp2 = new class01(pattern, 256);
int offset2 = kmp2.search(text); StdOut.println("text: " + txt); // 输出原文
StdOut.print("pattern: ");
for (int i = 0; i < offset1; i++) // 匹配的前导空格
StdOut.print(" ");
StdOut.println(pat); StdOut.print("pattern: ");
for (int i = 0; i < offset2; i++)
StdOut.print(" ");
StdOut.println(pat);
}
}
● Boyer - Moore 无回溯匹配
package package01; import edu.princeton.cs.algs4.StdOut; public class class01
{
private final int R;
private int[] right; // 回溯控制数组
private char[] pattern;
private String pat; public class01(String inputPat)
{
R = 256;
pat = inputPat;
int m = pat.length();
right = new int[R];
for (int c = 0; c < R; c++) // 初始化为 -1
right[c] = -1;
for (int j = 0; j < m; j++) // 记录每个字母在模式或者能够出现的最靠右的地方
right[pat.charAt(j)] = j;
} public class01(char[] inputPattern, int inputR)
{
R = inputR;
pattern = new char[inputPattern.length];
for (int j = 0; j < pattern.length; j++)
pattern[j] = inputPattern[j];
int m = pattern.length;
right = new int[R];
for (int c = 0; c < R; c++)
right[c] = -1;
for (int j = 0; j < m; j++)
right[pattern[j]] = j;
} public int search(String txt)
{
int m = pat.length(), n = txt.length(), skip;
for (int i = 0; i <= n - m; i += skip) // i 指向原文，向后移动
{
skip = 0;
for (int j = m - 1; j >= 0; j--) // j 指向模式，向前移动
{
if (pat.charAt(j) != txt.charAt(i + j)) // 若原文第 i+j 位 和模式第 j 位匹配，则自减 j 继续检查，若不匹配则要尝试跳转
{
skip = Math.max(1, j - right[txt.charAt(i + j)]); // 考虑原文第 i+j 位在匹配串中最右出现的位置，
break; // 若模式根本没有该字符，则 right[x] 等于 -1，skip 等于 1，原文前进 1 格，从模式头部开始重新匹配
} // 若模式有该字符，则 j - right[x] 等于该字符的右边的字符数（跳转后不需要检查的部分）
}
if (skip == 0) // j 循环检查完了 skip 都没变过，找到了，此时 i 指向原文中匹配的子字符串的开头
return i;
}
return n; // i 循环走完了都没找到
} public int search(char[] text)
{
int m = pattern.length, n = text.length, skip;
for (int i = 0; i <= n - m; i += skip)
{
skip = 0;
for (int j = m - 1; j >= 0; j--)
{
if (pattern[j] != text[i + j])
{
skip = Math.max(1, j - right[text[i + j]]);
break;
}
}
if (skip == 0)
return i;
}
return n;
} public static void main(String[] args)
{
String pat = args[0], txt = args[1];
char[] pattern = pat.toCharArray(), text = txt.toCharArray(); class01 bm1 = new class01(pat);
int offset1 = bm1.search(txt);
class01 bm2 = new class01(pattern, 256);
int offset2 = bm2.search(text); StdOut.println("text: " + txt);
StdOut.print("pattern: ");
for (int i = 0; i < offset1; i++)
StdOut.print(" ");
StdOut.println(pat); StdOut.print("pattern: ");
for (int i = 0; i < offset2; i++)
StdOut.print(" ");
StdOut.println(pat);
}
}
● Rabin - Karp 指纹匹配
package package01; import java.math.BigInteger;
import java.util.Random;
import edu.princeton.cs.algs4.StdOut; public class class01
{
private String pat;
private long patHash; // 模式的 hash 值
private int R; // 字符集基数
private int m; // 模式畅读
private long q; // 计算 hash 用的大素数
private long RM; // 中间值，等于 R^(m-1) % q public class01(char[] inputPattern, int inputR)
{
new class01(String.valueOf(inputPattern), inputR);
} public class01(String inputPat, int inputR)
{
pat = inputPat;
R = inputR;
m = pat.length();
q = longRandomPrime();
RM = 1; // 计算 RM
for (int i = 1; i <= m - 1; i++)
RM = (R * RM) % q;
patHash = hash(pat, m);
} private long hash(String key, int m) // 计算 hash 值，m 为字符串长度，hash = (Σ key[i] * R^(m-1-i)) % q，求和循环 i
{ // 递推 x[0] = key[0] % q，x[k+1] = (R * x[k] + key[k+1]) % q
long h = 0;
for (int j = 0; j < m; j++)
h = (R * h + key.charAt(j)) % q;
return h;
} public int search(String txt)
{
int n = txt.length();
if (n < m) // 原文太短
return n;
long txtHash = hash(txt, m); // 注意传入模式长度 m，表示计算 txt[0] ~ txt[m-1] 的 hash
if ((patHash == txtHash) && check(txt, 0)) // 原文头一段 hash 等于模式 hash，且通过了逐字比较，完成匹配
return 0;
for (int i = m; i < n; i++)
{
txtHash = (txtHash - RM * txt.charAt(i - m) % q + q) % q; // 更新原文的 hash，首先去掉第 i - m 位
txtHash = (txtHash*R + txt.charAt(i)) % q; // 然后加入第 i 位
int offset = i - m + 1; // 新的比较起点
if ((patHash == txtHash) && check(txt, offset)) // 同上，通过 hash 比较和逐字比较，完成匹配
return offset;
}
return n; // 没有匹配
} private static long longRandomPrime() // 生成大素数
{
return BigInteger.probablePrime(31, new Random()).longValue();
} private boolean check(String txt, int i) // 复查原文 txt[i] ~ txt[i+m-1] 是否匹配模式
{
for (int j = 0; j < m; j++)
{
if (pat.charAt(j) != txt.charAt(i + j))
return false;
}
return true;
} public static void main(String[] args)
{
String pat = args[0], txt = args[1];
class01 searcher = new class01(pat, 256);
int offset = searcher.search(txt); StdOut.println("text: " + txt);
StdOut.print("pattern: ");
for (int i = 0; i < offset; i++)
StdOut.print(" ");
StdOut.println(pat);
}
}