【数据结构】串与数组（二）-阿里云开发者社区

【数据结构】串与数组（二）

2022-09-22 115

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 【数据结构】串与数组

4.4.5 KMP算法：求公共前后缀 next数组 -- 推导

当我们准备求公共前后缀时，主串和模式串具有相同的内容，所以只需要看模式串。
实例1：模式串："abcabc"
提前将模式进行处理（预判）：将每一个字符假设不匹配时，公共前后缀提前记录下来，形成一个表格。
第一个位置：-1
第二个位置：0
使用next数组，记录统计好的表格。

4.4.6 KMP算法：求公共前后缀 next数组 -- 算法演示

实例1：模式串："abcabc"

4.4.7 KMP算法：求公共前后缀 next数组 -- 算法

/** 获得next数组* @param T 模式串* return 返回next数组*/publicint[] getNext(IStringT) {
//1. 创建数组，与模式串字符个数一致int[] next=newint[T.length()];       
intj=1;                              // 串的指针intk=0;                              // 模式串的指针（相同字符计数器）// 2 默认情况next[0] =-1;                           
next[1] =0;
// 3 准备比较while( j<T.length() -1 ) {            // 比较倒数第二个字符if(T.charAt(j) ==T.charAt(k)) {    // 连续有字符相等next[j+1] =k+1;
j++;
k++;
        } elseif (k==0) {
next[j+1] =0;
j++;
        } else {        //k不是零k=next[k];                //p119 数学推导        }
    }
// 4 处理完成，返回数组returnnext;
}

4.4.8 KMP算法：next数组使用

主串：ababababaaa
模式串：ababaaa

next数组

4.4.9 KMP算法

/** this 当前串，也就是主串 (this.length() 主串长度)* @param T 模式串 (T.length() 模式串长度)* @param start 从主串中开始位置，例如："abaababaaa".index_KMP("ababaaa",0);*/publicintindex_KMP(IStringT, intstart) {
//1 准备工作：next数组、指针int[] next=getNext(T);            //1.1 获得模式的next数组inti=start;                      //1.2 主串指针intj=0;                          //1.3 模式串的指针//2 字符比较移动while(i<this.length() &&j<T.length()) {    //2.1 串小于长度if(j==-1||//2.2.1 第一个字符不匹配，直接跳过this.charAt(i) ==T.charAt(j)) {//2.2.2 字符匹配i++;
j++;
        } else {
j=next[j];                        //2.3 移动模式串        }
    }
//3 处理结果if(j<T.length()) {                //3.1 移动位置没有模式串长，不匹配return-1;
    } else {
returni-T.length();          //3.2 匹配，目前在串后面，需要移动首字符    }
}