package kmpclient;
import java.io.UnsupportedEncodingException;
import java.util.LinkedList;
public class ByteKMP {
private static final int R = 255;
private static final String DEFAULT_CHARSET = "UTF-8";
private final int[][] dfa;
private final int patLen;
private int curMatchPos = 0;
public ByteKMP(byte[] pat) throws UnsupportedEncodingException {
patLen = pat.length;
// build DFA from pattern
int M = pat.length;
dfa = new int[R][M];
dfa[pat[0] & 0xff][0] = 1;
for (int X = 0, j = 1; j < M; j++) {
for (int c = 0; c < R; c++)
dfa[c][j] = dfa[c][X]; // Copy mismatch cases.
dfa[pat[j] & 0xff][j] = j + 1; // Set match case.
X = dfa[pat[j] & 0xff][X]; // Update restart state.
}
}
public int search(byte[] msg) {
int M = patLen;
int N = msg.length;
int i, j;
for (i = 0, j = curMatchPos; i < N && j < M; i++) {
j = dfa[msg[i] & 0xff][j];
}
if (j == M) {
curMatchPos = 0;
return i - M; // found
}
curMatchPos = j;
return N; // not found
}
public static void main(String[] args) throws UnsupportedEncodingException {
int a = -27 % 255;
testEnglishStr();
testChineseStr();
}
private static void testChineseStr() throws UnsupportedEncodingException {
LinkedList