package com.test.test.kmp;import java.util.Random;public class KMPTest {	public static void main(String[] args) {		test();	}		//	public static void test() {		//		int allLen = 8000000;		int subLen = 11;		int charLen = 4;		String cl = buildString(charLen);		int times = 50;		//		testMatch(allLen, subLen, cl, times);	}		public static void testMatch(int allLen, int subLen, String cl, int times){		int allBF = 0;		int allString = 0;		int allKMP = 0;		int allGC = 0;		int allbuild = 0;		int alltoArray = 0;				long start = System.currentTimeMillis();				System.out.println("--------------------------");		for (int i = 0; i < times; i++) {			// 1. 構(gòu)造字符串的損耗			long buildStart = System.currentTimeMillis();			String sub = buildString(subLen, cl);			String all = buildString(allLen, sub) +sub;			long buildEnd = System.currentTimeMillis();			allbuild += (buildEnd - buildStart);			// 2. toCharArray的損耗			long toArrayStart = System.currentTimeMillis();			char[] allArray = all.toCharArray();			char[] subArray = sub.toCharArray();			long toArrayEnd = System.currentTimeMillis();			alltoArray += (toArrayEnd - toArrayStart);			//			long startBF = System.currentTimeMillis();			int indexBF = bfIndexOf(all, sub);			long endBF = System.currentTimeMillis();			//			long timeoutBF = endBF - startBF;			allBF += timeoutBF;			System.gc();			allGC += (System.currentTimeMillis() - endBF);				//			long startString = System.currentTimeMillis();			int indexString = stringIndexOf(all, sub);			long endString = System.currentTimeMillis();			//			long timeoutString = endString - startString;			allString += timeoutString;			System.gc();			allGC += (System.currentTimeMillis() - endString);						//			long startKMP = System.currentTimeMillis();			//int indexKMP = kmpIndexOf(all, sub);			int indexKMP = KMP_Index(allArray, subArray);			long endKMP = System.currentTimeMillis();			//			long timeoutKMP = endKMP - startKMP;			allKMP += timeoutKMP;			System.gc();			allGC += (System.currentTimeMillis() - endKMP);						//			//System.out.println("all="+all.substring(0,100)+" ......");			//System.out.println("sub="+sub);			//			//System.out.println("indexBF="+indexBF+";耗時: "+timeoutBF+"ms");			//System.out.println("indexString="+indexString+";耗時: "+timeoutString+"ms");			if(indexBF == indexString && indexKMP == indexString){				//System.out.println("!!!!對比相等。");			} else {				throw new RuntimeException("對比出錯.");			}						//			if(i % 20 == 10){				System.out.println(i+"次bfIndexOf= "+allBF+"ms");				System.out.println(i+"次stringIndexOf= "+allString+"ms");				System.out.println(i+"次KMPIndexOf= "+allKMP+"ms");				System.out.println(i+"次allbuild= "+allbuild+"ms");				System.out.println(i+"次alltoArray= "+alltoArray+"ms");				System.out.println(i+"*3次,GC= "+allGC+"ms");				long end = System.currentTimeMillis();				long allTime = end-start;				long lossTime = allTime - (allBF+allString+allKMP+allGC);				System.out.println(i+"次,所有總計耗時: "+(allTime)+"ms; 損耗:" + lossTime +"ms; 損耗比: " +((0.0+lossTime)/allTime * 100)+"%");				System.out.println("--------------------------");			}					}		//		System.out.println(times+"次bfIndexOf;總計耗時: "+allBF+"ms");		System.out.println(times+"次stringIndexOf;總計耗時: "+allString+"ms");		System.out.println(times+"次KMPIndexOf;總計耗時: "+allKMP+"ms");		System.out.println(times+"次allbuild= "+allbuild+"ms");		System.out.println(times+"次alltoArray= "+alltoArray+"ms");		System.out.println(times+"*3次,GC;總計耗時: "+allGC+"ms");		long end = System.currentTimeMillis();		long allTime = end-start;		long lossTime = allTime - (allBF+allString+allKMP+allGC);		System.out.println(times+"次,所有總計耗時: "+(allTime)+"ms; 損耗:" + lossTime +"ms; 損耗比: " +((0.0+lossTime)/allTime * 100)+"%");		System.out.println("--------------------------");			}		//			// 構(gòu)建字符	public static String buildString(int len){		return buildString(len, null);	}	public static String buildString(int len, String sub){		//		final int TYPE_NUMBER = 0;		final int TYPE_LOWERCASE = 1;		final int TYPE_UPPERCASE = 2;		//		long seed = System.nanoTime();		Random random = new Random(seed);		//		//		StringBuilder builder = new StringBuilder();		for (int i = 0; i < len; i++) {			//			int type = random.nextInt(3);// 0-2			int cvalue = 0;			if(TYPE_NUMBER == type){				cvalue = '0' + random.nextInt(10);// 0~(n-1)			} else if(TYPE_LOWERCASE == type){				cvalue = 'a' + random.nextInt(26);// 0~(n-1)			} else if(TYPE_UPPERCASE == type){				cvalue = 'A' + random.nextInt(26);// 0~(n-1)			} else {				throw new RuntimeException(Random.class.getName()+"#newxtInt(int);Wrong!");			}			//			//cvalue = 'A' + random.nextInt(26);// 0~(n-1)			//			char c = (char)cvalue;			if(null != sub && sub.length() > 1){				int index = random.nextInt(sub.length());				c = sub.charAt(index);			}			//String s = String.valueOf(c);			builder.append(c);			//		}		//		return builder.toString();	}			/**	 * Java自帶的方法,內(nèi)部實現(xiàn)了	 * @param all	 * @param sub	 * @return	 */	public static int stringIndexOf(String all, String sub){		// 防御式編程		if(null == all || null== sub){			return -1;		}		// 調(diào)用Java的String方法		return all.indexOf(sub);	}			/**	 * BF算法	 * @param all	 * @param sub	 * @return	 */	public static int bfIndexOf(String all, String sub){		// 防御式編程		if(null == all || null== sub){			return -1;		}		//		int lenAll = all.length();		int lenSub = sub.length();		int i = 0;		while (i < lenAll) {			// 從i下標開始對比			int j = 0;			while (j < lenSub) {				//				char all_i = all.charAt(i);				char sub_j = sub.charAt(j);				if(all_i == sub_j){					// 相等則繼續(xù)對比下一個字符					i++;					j++; // 這個增長很重要				} else {					// 否則跳出內(nèi)層循環(huán)					break;				}			}			// 如果 j 增長到和 lenSub相等,則匹配成功			if(lenSub == j){				return i - lenSub;			} else {				i = 1+i - j; // 回溯 i			}		}		//		return -1;	}		/**	 * KMP 算法	 * @param all	 * @param sub	 * @return	 */	public static int kmpIndexOf(String all, String sub){		//		char[] allArray = all.toCharArray(); 		char[] subArray = sub.toCharArray(); 		//		return KMP_Index(allArray, subArray);	}  /**    * 獲得字符串的next函數(shù)值    *    * @param t    *      字符串    * @return next函數(shù)值    */   public static int[] next(char[] t) {     int[] next = new int[t.length];     next[0] = -1;     int i = 0;     int j = -1;     while (i < t.length - 1) {       if (j == -1 || t[i] == t[j]) {         i++;         j++;         if (t[i] != t[j]) {           next[i] = j;         } else {           next[i] = next[j];         }       } else {         j = next[j];       }     }     return next;   }    /**    * KMP匹配字符串    *    * @param allArray    *      主串    * @param subArray    *      模式串    * @return 若匹配成功，返回下標，否則返回-1    */ 	public static int KMP_Index(char[] allArray, char[] subArray) {     int[] next = next(subArray);     int i = 0;     int j = 0;     while (i <= allArray.length - 1 && j <= subArray.length - 1) {       if (j == -1 || allArray[i] == subArray[j]) {         i++;         j++;       } else {         j = next[j];       }     }     if (j < subArray.length) {       return -1;     } else       return i - subArray.length; // 返回模式串在主串中的頭下標   } }

--------------------------10次bfIndexOf= 94ms10次stringIndexOf= 56ms10次KMPIndexOf= 76ms10次allbuild= 5870ms10次alltoArray= 137ms10*3次,GC= 155ms10次,所有總計耗時: 6388ms; 損耗:6007ms; 損耗比: 94.03569192235442%--------------------------30次bfIndexOf= 365ms30次stringIndexOf= 222ms30次KMPIndexOf= 295ms30次allbuild= 16452ms30次alltoArray= 395ms30*3次,GC= 452ms30次,所有總計耗時: 18184ms; 損耗:16850ms; 損耗比: 92.66388033435987%--------------------------50次bfIndexOf;總計耗時: 550ms50次stringIndexOf;總計耗時: 335ms50次KMPIndexOf;總計耗時: 450ms50次allbuild= 26501ms50次alltoArray= 637ms50*3次,GC;總計耗時: 734ms50次,所有總計耗時: 29211ms; 損耗:27142ms; 損耗比: 92.91705179555647%--------------------------