package algorithm;
class Kmp{
public int index(String a, String b){
if(a == null || b == null || a.length() < b.length())
return -;
int temp ;
for(int i = , j = ; i < a.length();){
temp = i;
if(a.charAt(i) == b.charAt(j)){
i++;
j++;
if(j == b.length()){
return i - b.length();
}
}else{
i = temp + ;
j = ;
}
}
return -;
}
public int violentmatch(String a, String b){
int alen = a.length();
int blen = b.length();
int i = ;
int j = ;
while(i < alen && j < blen){
if(a.charAt(i) == b.charAt(j)){
i++;
j++;
}else{
i = i - j + ;
j = ;
}
}
if(j == blen)
return i - j;
return -;
}
public void getnext(String des, int next[]){
int blen = des.length();
int k = -; //字首
int j = ; //字尾
next[j] = k;
while(j < blen - ){
if(k == - || des.charAt(j) == des.charAt(k)){
j++;
k++;
next[j] = k;
}else{
k = next[k];
}
}
}
public void getnextval(String des, int next[]){
int blen = des.length();
int k = -;
int j = ;
next[j] = k;
while(j < blen - ){
if(k == - || des.charAt(j) == des.charAt(k)){
k++;
j++;
if(des.charAt(j) != des.charAt(k))
next[j] = k;
else
next[j] = next[k];
}else{
k = next[k];
}
}
}
public int kmpSearch(String src, String des){
int next[] = new int[des.length()+];
// getnext(des, next);
getnextval(des, next);
int alen = src.length();
int blen = des.length();
int i = ;
int j = ;
while(i < alen && j < blen){
if(j == - || src.charAt(i) == des.charAt(j)){
i++;
j++;
}else{
j = next[j];
}
}
if(j == blen)
return i - j;
return -;
}
//BM算法主函數
public int bmSearch(char[] src, char[] des){
if(des.length == )
return ;
int[] charTable = makeCharTable(des);
int[] gsTable = makeGsTable(des);
int i = , j;
while(i <= src.length - des.length){
for(j = des.length - ; j >= && des[j] == src[j + i]; j--)
if(j == )
return i;
i += Math.max(gsTable[j], charTable[src[i]] - (des.length - - j));
}
return -;
}
//BM算法主函數2
public int bmsearch2(char[] src, char[] des){
int[] charTable = makeCharTable(des);
int[] gsTable = makeGsTable(des);
for(int i = des.length - , j; i < src.length;){
for(j = des.length - ; j >= && src[i] == des[j]; i--, j--)
if(j == )
return i;
i += Math.max(gsTable[j], charTable[src[i]] - (des.length - - j));
}
return -;
}
//模式串預處理
//壞字元規則
public int[] makeCharTable(char[] des){
int[] table = new int[];
for(int i = ; i < ; i++)
table[i] = des.length;
for(int i = ; i < des.length - ; i++)
table[des[i]] = des.length - - i;
return table;
}
//好字尾規則
public int[] makeSuffixTable(char[] des){
int suffix[] = new int[des.length];
suffix[des.length - ] = des.length;
for(int i = des.length - ; i >= ; i--){
int q = i;
while(q >= && des[q] == des[des.length - -(i - q)])
q--;
suffix[i] = i - q;
}
return suffix;
}
//good suffix table
public int[] makeGsTable(char des[]){
int i, j, suffix[] = makeSuffixTable(des);
int gs[] = new int[des.length];
//沒有比對好字尾，找不到最大字首
for(i = ; i < des.length; i++)
gs[i] = des.length;//好字尾數組初始化
j = ;
//沒有比對好字尾，但是找到最大字首
for(i = des.length -; i >= ; i--)
if(suffix[i] == i+) //找到一個最大字首
for(; j < des.length - - i; j++)
if(gs[j] == des.length)
gs[j] = des.length - - i;
//模式串中有子串比對上好字尾
for(i = ; i <= des.length - ; i++)
gs[des.length - - suffix[i]] = des.length - - i;
return gs;
}
public int sundaySearch(char[] src, char[] des){
int i = , j = ;
int temp, offset;
int[] charTable = makeCharTable(des);
while(i < src.length && j < des.length){
temp = i;
while(src[i] == des[j]){
i++;
j++;
if(j == des.length)
return temp;
}
offset = charTable[src[temp + des.length]] + ;
i += offset;
j = ;
}
return -;
}
}
public class KMP1 {
/*public static int indexOf(char[] haystack, char[] needle) {
if (needle.length == 0) {
return 0;
}
int charTable[] = makeCharTable(needle);
int offsetTable[] = makeOffsetTable(needle);
System.out.println("CharTable: ");
for(int t1 : charTable){
System.out.print(t1 + " ");
}
System.out.println();
System.out.println("OffSetTable: ");
for(int t2 : offsetTable){
System.out.print(t2 + " ");
}
System.out.println();
for (int i = needle.length - 1, j; i < haystack.length;) {
for (j = needle.length - 1; needle[j] == haystack[i]; --i, --j) {
if (j == 0) {
System.out.println("比對成功 位置 i = ");
return i;
}
}
// i += needle.length - j; // For naive method
i += Math.max(offsetTable[needle.length - 1 - j], charTable[haystack[i]]);
}
return -1;
}
*//**
* Makes the jump table based on the mismatched character information.
*//*
private static int[] makeCharTable(char[] needle) {
final int ALPHABET_SIZE = 256;
int[] table = new int[ALPHABET_SIZE];
for (int i = 0; i < table.length; ++i) {
table[i] = needle.length;
}
for (int i = 0; i < needle.length - 1; ++i) {
table[needle[i]] = needle.length - 1 - i;
}
return table;
}
*//**
* Makes the jump table based on the scan offset which mismatch occurs.
*//*
private static int[] makeOffsetTable(char[] needle) {
int[] table = new int[needle.length];
int lastPrefixPosition = needle.length;
for (int i = needle.length - 1; i >= 0; --i) {
if (isPrefix(needle, i + 1)) {
lastPrefixPosition = i + 1;
}
table[needle.length - 1 - i] = lastPrefixPosition - i + needle.length - 1;
}
for (int i = 0; i < needle.length - 1; ++i) {
int slen = suffixLength(needle, i);
table[slen] = needle.length - 1 - i + slen;
}
return table;
}
*//**
* Is needle[p:end] a prefix of needle?
*//*
private static boolean isPrefix(char[] needle, int p) {
for (int i = p, j = 0; i < needle.length; ++i, ++j) {
if (needle[i] != needle[j]) {
return false;
}
}
return true;
}
*//**
* Returns the maximum length of the substring ends at p and is a suffix.
*//*
private static int suffixLength(char[] needle, int p) {
int len = 0;
for (int i = p, j = needle.length - 1;
i >= 0 && needle[i] == needle[j]; --i, --j) {
len += 1;
}
return len;
}*/
public static void main(String[] args) {
Kmp k = new Kmp();
String src = "ABCGDETYIBCDEKKWSBCDE";
// String src = "BCDE";
String des = "BCDE";
int pos1 = k.index(src, des);
int pos2 = k.violentmatch(src, des);
int kmppos = k.kmpSearch(src, des);
int bmpos = k.bmSearch(src.toCharArray(), des.toCharArray());
int bmpos2 = k.bmsearch2(src.toCharArray(), des.toCharArray());
int sundaypos = k.sundaySearch(src.toCharArray(), des.toCharArray());
System.out.println("String.indexOf(): " + src.indexOf(des));
System.out.println("模式比對1：" + pos1);
System.out.println("模式比對2：" + pos2);
System.out.println("kmp: " + kmppos);
System.out.println("my bm: " + bmpos);
System.out.println("my bm 2 : "+ bmpos2);
System.out.println("sunday: " + sundaypos);
// System.out.println("BM other："+ indexOf(src.toCharArray(), des.toCharArray()));
}
}
![goalng nil interface淺析持續學習[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)