一、暴力子字符串查找算法：
public class Baoli
{
public static int search(String pattern, String txt)
{
int M = pattern.length();
int N = txt.length();
for (int i = 0; i < N-M; i++)
{
int j;
for (j = 0; j < M; j++)
if (txt.charAt(i+ j) != pattern.charAt(j))
break;
if (j == M) return i;
}
return N;
}
public static int search2(String pattern, String txt)
{
int j, M = pattern.length();
int i, N = txt.length();
for (i = 0, j = 0; i < N&&j < M; i++)
{
if (txt.charAt(i) == pattern.charAt(j))j++;
else
{i -= j; j = 0;}
}
if (j == M) return i - M;
else return N;
}
}
二、KMP字符串查找算法：
public class KMP
{
private int[][] dfa;
private String pat;
public KMP(String pat)
{
this.pat = pat;
int M = pat.length();
int R = 256;
dfa = new int[R][M];
dfa[pat.charAt(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[pat.charAt(j)][j] = j+1;
X = dfa[pat.charAt(j)][X];
}
}
public int search(String txt)
{
int i,j, N = txt.length(),M = pat.length();
for (i = 0, j= 0; i < N && j < M ; i++)
j = dfa[txt.charAt(i)][j];
if (j == M) return i - M;
else return N;
}
}
三、Booyer-Moore字符串匹配算法：
public class BoyerMoore
{
private int[] right;
private String pat;
public BoyerMoore(String pat)
{
this.pat = pat;
int R = 256;
int M = pat.length();
right = new int[R];
for (int c = 0; c < R; c++)
right[c] = -1;
for (int j = 0; j < M; j++)
right[pat.charAt(j)] = j;
}
public int search(String txt)
{
int M = pat.length();
int N = txt.length();
int skip;
for (int i = 0; i <= N - M; i += skip)
{
skip = 0;
for (int j = M - 1; j >= 0; j--)
{
if (txt.charAt(i+j) != pat.charAt(j))
{
skip = j - right[txt.charAt(i+j)];
if (skip < 1) skip = 1;
break;
}
}
if (skip == 0) return i;
}
return N;
}
}
三、Rabin-Karp指纹字符串查找算法：
public class RabinKarp
{
private int R = 256;
private String pat;
private int M;
private int Q;
private long RM;
private long patHash;
public RabinKarp(String pat)
{
this.pat = pat;
this.M = pat.length();
Q = longRandomPrime();
RM = 1;
for (int i = 0; i < M; i++)
{
RM = (RM * R) % Q;
}
patHash = hash(pat, M);
}
private long hash(String key, int M)
{
long h = 0;
for (int i = 0; i < M; i++)
h = (h * R + key.charAt(i)) % R;
return h;
}
public boolean check(int i)
{return true;}
public int search(String txt)
{
int N = txt.length();
long txtHash = hash(txt, M);
if (txtHash == patHash && check(0)) return 0;
for (int i = M; i < N; i ++)
{
txtHash = (txtHash - txt.charAt(i - M)* RM + Q) % Q;
txtHash = (txtHash * R + txt.charAt(i)) % Q;
if (txtHash == patHash && check(i - M + 1)) return i - M + 1;
}
return N;
}
}