kmp算法java实现并计算实现速度

kmp算法java实现并计算实现速度

1、普通的字符匹配没有什么奇效
2、牛逼的算法都是用在特殊的地方

package com.ccc;

public class Test {

	public static void main(String arg[]) {
		//毫秒 System.currentTimeMillis()
		//纳秒 System.nanoTime()
		long start1 = System.nanoTime();
		plain("sdflajsabcdes9afslsa", "abcde");
		long end1 = System.nanoTime();
		p("普通算法："+(end1-start1));
		KMP("sdflajsabcdes9afslsa", "abcde");
		long end2 = System.nanoTime();
		p("KMP算法："+(end2-start1));
	}

	/**
     * 朴素模式匹配
     * 
     * @param source 目标串
     * @param pattern 模式串
     */
   public static void plain(String source, String pattern) {
        int res=0;
        int sourceLength=source.length();
        int patternLength=pattern.length();
        for(int i=0;i<=(sourceLength-patternLength);i++){
            res++;
            String str=source.substring(i, i+patternLength);
            if(str.equals(pattern)){
                p("朴素模式：匹配成功");
                break;
            }
        }
        p("朴素模式：一共匹配"+res+"次数");
    }

	// KMP算法实现
	private static void KMP(String source, String pattern) {
		int[] N = getN(pattern);
		int res = 0;
		int sourceLength = source.length();
		int patternLength = pattern.length();
		for (int i = 0; i <= (sourceLength - patternLength);) {
			res++;
			String str = source.substring(i, i + patternLength);// 要比较的字符串
			p(str);
			int count = getNext(pattern, str, N);
			p("移动" + count + "步");
			if (count == 0) {
				p("KMP：匹配成功");
				break;
			}
			i = i + count;
		}
		p("KMP：一共匹配" + res + "次数");
	}

	/**
	 * 得到下一次要移动的次数
	 * 
	 * @param pattern
	 * @param str
	 * @param N
	 * @return 0,字符串匹配；
	 */
	private static int getNext(String pattern, String str, int[] N) {
		int n = pattern.length();
		char v1[] = str.toCharArray();
		char v2[] = pattern.toCharArray();
		int x = 0;
		while (n-- != 0) {
			if (v1[x] != v2[x]) {
				if (x == 0) {
					return 1;// 如果第一个不相同，移动1步
				}
				return x - N[x - 1];// x:第一次出现不同的索引的位置，即j
			}
			x++;
		}
		return 0;
	}

	private static int[] getN(String pattern) {
		char[] pat = pattern.toCharArray();
		int j = pattern.length() - 1;
		int[] N = new int[j + 1];
		for (int i = j; i >= 2; i--) {
			N[i - 1] = getK(i, pat);
		}
		for (int a : N)
			p(a);
		return N;
	}

	private static int getK(int j, char[] pat) {
		int x = j - 2;
		int y = 1;
		while (x >= 0 && compare(pat, 0, x, y, j - 1)) {
			x--;
			y++;
		}
		return x + 1;
	}

	private static boolean compare(char[] pat, int b1, int e1, int b2, int e2) {
		int n = e1 - b1 + 1;
		while (n-- != 0) {
			if (pat[b1] != pat[b2]) {
				return true;
			}
			b1++;
			b2++;
		}
		return false;
	}

	public static void p(Object obj) {
		System.out.println(obj);
	}

}