注册 登录
  • 欢迎访问开心洋葱网站,在线教程,推荐使用最新版火狐浏览器和Chrome浏览器访问本网站,欢迎加入开心洋葱 QQ群
  • 为方便开心用户,开心洋葱官网已经开启复制功能!
  • 欢迎访问开心洋葱网站,手机也能访问哦~欢迎加入开心洋葱多维思维学习平台 QQ群
  • 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏开心洋葱吧~~~~~~~~~~~~~!
  • 由于近期流量激增,小站的ECS没能经的起亲们的访问,本站依然没有盈利,如果各位看如果觉着文字不错,还请看官给小站打个赏~~~~~~~~~~~~~!

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

JAVA相关 开心洋葱 1843次浏览 已收录 0个评论 手机上查看

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);
    }

}


开心洋葱 , 版权所有丨如未注明 , 均为原创丨未经授权请勿修改 , 转载请注明kmp算法java实现并计算实现速度
喜欢 (0)
[开心洋葱]
分享 (0)
关于作者:
开心洋葱,开心洋葱头,水墨

您必须 登录 才能发表评论!

……