灯火互联
管理员
管理员
  • 注册日期2011-07-27
  • 发帖数41778
  • QQ
  • 火币41290枚
  • 粉丝1086
  • 关注100
  • 终身成就奖
  • 最爱沙发
  • 忠实会员
  • 灌水天才奖
  • 贴图大师奖
  • 原创先锋奖
  • 特殊贡献奖
  • 宣传大使奖
  • 优秀斑竹奖
  • 社区明星
阅读:7074回复:0

KMP字符串匹配算法

楼主#
更多 发布于:2013-11-04 11:00

publicclassKMP {

    staticint[] next;    /**

     *

     * @param t  模式串,求得模式串回溯的next函数

     */

    staticvoidnext(String t) {

        next = newint[t.length()];

        next[0] = -1;

        intj = -1;

        inti = 0;

        while(i < t.length()-1) {

            if(j == -1|| t.charAt(i) == t.charAt(j)) {

                i++;

                j++;

                if(t.charAt(i) == t.charAt(j)){

                    next = next[j];

                }else{

                    next = j;

                }

            }else{

                j = next[j];

            }

        }    }

    /**     *

     * @param s 主串

     * @param t 模式串

     * @param pos 从主串的pos下标位置开始匹配

     */

    staticintmatch(String s,String t,intpos){

        inti=pos;

        intj=0;

        while(i<s.length()&& j<t.length()){

            if(j==-1|| s.charAt(i)==t.charAt(j)){

                i++;

                j++;

            }else{

                j = next[j];

            }

        }

        if(j>t.length()-1){

            returni-j;

        }else{

            return-1;

        }    }

    publicstaticvoidmain(String[] args) {

        String s = "aaaasad";

        String t = "sa";

        next(t);

        System.out.println(match(s,t,0));

    }}


喜欢0 评分0
游客

返回顶部