-
KMP算法中的next函数值求法的原理5
RT，是next函数值求法的原理！不是求法！谢谢！public int[] getNext(char[] pattern) { int pattern_len=pattern.length; int[] next=new int[pattern_len]; next[0]=-1;next[1]=0; for (int i = 2; i < pattern_len; i++) { int j=i; while(j>1) { if (pattern[i-1]==pattern[next[j-1]]) { next[i]=next[j-1]+1; break; }else { j=next[j-1]; } } if (j==1) { next[i]=1; } } return next; }2013年9月26日 00:23
添加评论
关注(0)3个答案 按时间排序 按投票排序
-
采纳的答案
http://www.cppblog.com/oosky/archive/2006/07/06/9486.html
2013年9月26日 15:28
-
你这程序有问题，我测试了下，返回的是-1,0,0,0,0....
这程序的目的是什么？
public class NextTest {
public static int[] getNext(char[] pattern) {
int pattern_len=pattern.length;
int[] next=new int[pattern_len];
next[0]=-1;next[1]=0;
for (int i = 2; i < pattern_len; i++) {
int j=i;
while(j>1) {
if (pattern[i-1]==pattern[next[j-1]]) {
next[i]=next[j-1]+1;
break;
}else {
j=next[j-1];
}
}
if (j==1) {
next[i]=1;
}
}
return next;
}
public static void main(String[] args){
char[] a={'a','e','f','g','w'};
int[] b= getNext(a);
for(int i=0;i<b.length;i++){
System.out.println(b[i]);
}
}
}2013年9月26日 11:31
相关推荐
在 KMP 算法中，使用 next 数组来记录模式串 T 中每个字符的模式函数值。next[i] 表示模式串 T 中从 0 到 i 的子串和模式串 T 的前缀的最长公共后缀的长度。 KMP 算法的时间复杂度为 O(m+n)，远远优于简单匹配算法...
* 定义：next值表示模式串T中某个位置的模式函数值。 * 例二：求T=？abcab？的模式函数的值。 * 设T=？abcab？，S ＝？abcadcabcab？，利用KMP算法进行匹配，几次匹配成功？存在什么问题？ 八、结论 通过本课例...
以此类推，直到模式T中的每个字符依次和主串S中的一个连续字符序列相等，则称匹配成功，则函数值为和模式T中的第一个字符相等的字符在主串S中的序号，否则称匹配不成功，函数值为0.而对于模式匹配的KMP算法可以在O(n...
"KMP算法详解" 一、KMP字符串模式匹配算法 KMP字符串模式匹配算法是一种高效的字符串模式匹配算法，能够在一个字符串中快速地定位另一个字符串。该算法的时间复杂度为O(m+n)，远远优于简单匹配算法的时间复杂度O(m...
即可通过算法分析模式串的`next[]`函数值，并形成`next[]`数组； 2. **规定**：`next[1]=0`； 3. **当j=1时**，如果此时的模式串与主串不匹配（`Si≠Pj`），那么`j`将退至`next[j]`位置，即`j=0`，此时，`i`与`j`...
KMP算法是字符串模式匹配中的经典算法之一，该算法的关键在于使用next数组来记录模式串中的模式函数值，从而避免了不必要的比较操作。该算法的时间复杂度为O(n+m)，其中n是目标字符串的长度，m是模式串的长度。KMP...
1. **部分匹配表（Next数组）**：KMP算法的关键在于构建一个部分匹配表，用于记录当模式串中的某个字符与主串中的字符不匹配时，模式串可以向前滑动的最大长度。例如，对于模式串 "abaabcac"，部分匹配表为 `next[1]...
具体思路为：next函数求出模式串向右滑动位数，再将模式串的str的next函数值 存入数组next。 具体实现代码如下： static void GetNextVal(string str, int [] next) { int i = 0; int j = -1; next[0] = -1; ...
- 视频教程如B站上的讲解，包括KMP算法计算next函数值、实例详解和易懂版本。 - 博客文章提供了详尽的解析，包括知乎上的通俗易懂解释、Next数组详解、原创的算法解析，以及对算法来龙去脉的阐述。 - 还有一些博客...
KMP字符串模式匹配通俗点说就是一种在一个字符串中定位另一个串的高效算法。简单匹配算法的时间复杂度为O(m*n);KMP匹配算法。可以证明它的时间复杂度... // 求模式串T的next函数值并存入数组 next。 int j = 0, k = -1...
- `get_next(char *T)`：计算模式串 T 的 next 函数值，存储在 next 数组中。 - `index_KMP(char *s, char *T, int pos)`：使用 KMP 算法查找模式串 T 在主串 S 的位置。 - `compare(char *m, int k)`：对文件...
功能简介 本课件是一个动态演示数据结构算法执行过程的... （2）求Next 函数值(Get_next)和按Next 函数值进行匹配 (Index_KMP(next)) （3）求 Next 修正值(Get_nextval)和按 Next 修正值进行匹配(Index_KMP(nextval))
（2）求Next 函数值(Get_next)和按Next 函数值进行匹配 (Index_KMP(next)) （3）求 Next 修正值(Get_nextval)和按 Next 修正值进行匹配(Index_KMP(nextval)) 5． 稀疏矩阵 （1）矩阵转置 (Trans_Sparmat) （2）...
（2）求Next 函数值(Get_next)和按Next 函数值进行匹配 (Index_KMP(next)) （3）求 Next 修正值(Get_nextval)和按 Next 修正值进行匹配(Index_KMP(nextval)) 5． 稀疏矩阵 （1）矩阵转置 (Trans_Sparmat) （2）...
（2）求Next 函数值(Get_next)和按Next 函数值进行匹配 (Index_KMP(next)) （3）求 Next 修正值(Get_nextval)和按 Next 修正值进行匹配(Index_KMP(nextval)) 5． 稀疏矩阵 （1）矩阵转置 (Trans_Sparmat) （2）...
- **模式串的next和nextval函数值**：next数组记录了模式串中每个位置的最长前后缀长度，nextval数组则记录了对应位置的最长公共前后缀长度。 - **手工模拟KMP算法的执行过程**：在实际操作中，我们根据next数组，...
（2）求Next 函数值(Get_next)和按Next 函数值进行匹配 (Index_KMP(next)) （3）求 Next 修正值(Get_nextval)和按 Next 修正值进行匹配(Index_KMP(nextval)) 5． 稀疏矩阵 （1）矩阵转置 (Trans_Sparmat) （2）...
大学计算机科学与技术专业 数据结构课程 第四章 串 串的抽象数据类型的定义 串的表示和实现 串的模式匹配算法 一、简单算法 二、首尾匹配算法 三、...学会手工计算给定模式串的NEXT函数值和改进的NEXT函数值。