Algorithms for matching strings (without using RegularExpressions):
Sample code in JavaLanguage
/* 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 ();
},
},
See Also: ComparingDynamicVariables