Algorithms for matching strings (without using RegularExpression''''''s):

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
----
CategoryAlgorithm