Knuth-Morris-Pratt string matching algorithm

KNFAlgorithm

import java.util.Arrays;
import java.util.HashMap;

public class KNFAlgorithm {
	
	private static int[] getTable(String s) {
		char[] chars = s.toCharArray();
		int n = chars.length;
		HashMap<Character, Integer> map = new HashMap<>();
		int[] table = new int[n];
		
		int i = 0;
		while (i < n) {
			if (!map.containsKey(chars[i])) {
				map.put(chars[i], i + 1);
				table[i] = 0;
				i++;
			} else {
				int j = map.get(chars[i]) - 1;
				
				while ((i < n) && (chars[i] == chars[j])) {
					table[i] = ++j;
					i++;
				}
			}
		}
		
		return table;
	}
	
	private static boolean contains(String a, String b) {
		String smaller = a.length() <= b.length() ? a : b;
		String larger = a.length() > b.length() ? a : b;
		char[] ch1 = larger.toCharArray();
		char[] ch2 = smaller.toCharArray();
		int[] table = getTable(smaller);
		
		int i = 0;
		int j = 0;
		while (i < ch1.length) {
			j++;
			
			if (ch1[i] != ch2[j - 1]) {
				if (j == 1) {
					j = 0;
				} else {
					j = table[j - 2];
				}
			} else if (j == ch2.length) {
				return true;
			}
			
			i++;
		}
		
		return false;
	}
	
	public static void main(String[] args) {
		String a = "abcdeabdeabcdf";
		String b = "abcdf";
		
		System.out.println(contains(a, b));
	}
}