模式匹配-BF、KMP、JavaString.indexOf、BM大比拼

闲来无事,比比看。

 

/**

 * 模式匹配-BF、KMP、JavaString.indexOf、BM大比拼

 */

package javay.test;

 

import javay.util.PMBF;

import javay.util.PMBM;

import javay.util.PMKMP;

 

/**

 * 模式匹配-BF、KMP、JavaString.indexOf、BM大比拼

 * @author DBJ

 */

public class TestPM {

 

    /**

     * @param args

     */

    public static void main(String[] args) {

        /* */

        StringBuffer buf = new StringBuffer();

        long start_001 = System.currentTimeMillis();

        for (int i = 0; i < 10000000; i ++) {

            buf.append("abace");

        }

        buf.append("abcde");

        String src = buf.toString();

        long end_001 = System.currentTimeMillis();

        System.out.println("建目串消耗的时间" + (end_001 - start_001) + "毫秒");

 

        /* 模式串 */

        String ptn = "abcde";

        int pos = -1;

 

        /* Brute-Force */

        long start_01 = System.currentTimeMillis();

        pos = PMBF.patternMatch(srcptn);

        long end_01 = System.currentTimeMillis();

        System.out.println("BF 消耗的时间" + (end_01 - start_01) + "毫秒");

        System.out.println(pos);

 

        /* Knuth-Morris-Pratt */

        long start_02 = System.currentTimeMillis();

        pos = PMKMP.patternMatch(src, ptn);

        long end_02 = System.currentTimeMillis();

        System.out.println("KMP消耗的时间" + (end_02 - start_02) + "毫秒");

        System.out.println(pos);

 

        /* String */

        long start_03 = System.currentTimeMillis();

        pos = src.indexOf(ptn);

        long end_03 = System.currentTimeMillis();

        System.out.println("indexOf消耗的时间" + (end_03 - start_03) + "毫秒");

        System.out.println(pos);

 

        /* Boyer-Moore */

        long start_05 = System.currentTimeMillis();

        pos = PMBM.patternMatch(src, ptn);

        long end_05 = System.currentTimeMillis();

        System.out.println("BM 消耗的时间" + (end_05 - start_05) + "毫秒");

        System.out.println(pos);

    }

}

 

 

 

结果:

创建目标串消耗的时间:1248毫秒

 

BF 消耗的时间:1062毫秒

50000000

 

getNext消耗的时间:0毫秒

KMP1消耗的时间:874毫秒

KMP消耗的时间:874毫秒

50000000

 

indexOf消耗的时间:313毫秒

50000000

 

BM 消耗的时间:218毫秒

50000000

 

JavaString不错呀。

 


郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。