Matching Strings

Algorithms for matching strings (without using RegularExpressions):
/* Matching.java */ public class Matching {
public int match_brute_force (String text, String p) {
int i;
for (i = 0; i < text.length () - p.length (); i++) {
int j = 0;
while (j < p.length () && text.charAt (i + j) == p.charAt (j))
j++;
if (j == p.length ())
return i;
}

return -1;
}

/* Note: char of Java is 16 bit. */
public int match_boyer_moore (byte[] text, byte[] p) {
/*
 * Compute last[] table
 */

int last[] = new int[256];

for (int i = 0; i < 256; i++) {
last[i] = -1;
}

for (int i = 0; i < p.length; i++) {
last[p[i]] = i;
}

/*
 * Do matching
 */

int
 i = p.length - 1,
 j = p.length - 1;
while (i < text.length) {
if (text[i] == p[j]) {
if (j == 0)
return i;/* match! */
i--;
j--;
}
else {
int
 n, /* how many characters skip */
 l = last[text[i]];
n = j - l;
if (n < 0)
n = 1;
i = i + (p.length - 1) - j + n;
j = p.length - 1;
}
}

return -1;
}

public int match_knuth_morris_pratt (String text, String p) {
/*
 * Compute failure functions
 */

int f[] = new int[text.length ()];
f[0] = 0;

int i = 1, j = 0;
while (i < p.length ()) {
if (p.charAt (j) == p.charAt (i)) {
f[i] = j + 1;
i++;
j++;
}
else if (j > 0)
j = f[j - 1];
else {
f[i] = 0;
i++;
}
}

/*
 * Do matching
 */

i = 0; j = 0;
while (i < text.length ()) {
if (text.charAt (i) == p.charAt (j)) {
if (j == p.length () - 1)
return i - j;
i++;
j++;
}
else if (j > 0)
j = f[j - 1];
else
i++;
}

return -1;
}

/* Constructor */
Matching () {
int n;
String t = "abdadccbadadabacaa";
n = match_brute_force (t, "dadab"); assert n == 9 : "n = " + n;
n = match_brute_force (t, "aadab"); assert n < 0 : "n = " + n;

n = match_boyer_moore (t.getBytes (), "dadab".getBytes ()); assert n == 9 : "n = " + n;
n = match_boyer_moore (t.getBytes (), "aadab".getBytes ()); assert n < 0 : "n = " + n;

n = match_knuth_morris_pratt (t, "dadab"); assert n == 9 : "n = " + n;
n = match_knuth_morris_pratt (t, "abcdc"); assert n < 0 : "n = " + n;
}

public static void main (String[] argv) {
new Matching ();
}
}