东营局域网设计_电子简历表格 个人简历_怎么找推广渠道_最新注册域名查询

字符串的模式匹配算法（二）

next 数组的求解算法

手算方法

next[i] 中存放的data表示，当第 i 个元素匹配失败时，下一次匹配时令 j = data

对于任何一个模式串，第一个字符不匹配时，只能匹配下一个子串，因此next[1]永远等于0

对于任何一个模式串，第二个字符不匹配时，应尝试匹配模式串的第一个元素，因此next[2]永远等于1

在后面的过程中，在不匹配的位置前画一条分界线，模式串一步一步往后退，直到分界线之前能对上(首尾重合),或模式串完全跨过分界线为止。

算法思路

1. 初始化：
   • i初始化为1，表示当前正在计算next数组的位置（在C语言中数组索引从0开始，但通常next数组的第一个位置next[0]是未使用的，因此从next[1]开始）。
   • j初始化为0，表示当前匹配的最长公共前后缀的长度。
2. next[1]设置为0，因为第一个字符之前没有字符，不存在前后缀。
3. 进入一个循环，该循环会一直执行，直到i等于模式串T的长度。
4. 在循环内部，有一个条件判断：
   • 如果j等于0或者当前模式串中的字符T.ch[i]等于T.ch[j]，说明找到了一个匹配的前后缀。此时，将i和j都增加1，并将next[i]设置为j，表示在位置i之前的最长公共前后缀长度为j。
5. 如果j不等于0且当前字符T.ch[i]不等于T.ch[j]，说明当前字符不匹配，需要根据next数组回退j的值。j被设置为next[j]，这是因为在位置j之前的最长公共前后缀的下一个位置就是next[j]，我们可以从这个位置开始比较，避免从头开始。
6. 循环继续，直到计算出所有位置的next值。

算法实现

void get_next(SString T, int next[]){int i = 1, j = 0;next[1] = 0;while(i < T.length){if(j == 0 || T.ch[i] == T.ch[j]){++i;++j;next[i] = j; // 若P[i] = P[j]，则next[j+1] = next[j] + 1}elsej = next[j]; // 否则令j = next[j]，循环继续}
}

KMP算法的进一步优化 – nextval 数组

手算方法

先求next数组，再由next数组求nextval数组

若出现pj=Pnext[j],则需要再次递归，将next[j]修正为next[next[j]],直至两者不相等为止，修正后的数据存放在nextval数组中

算法思路

1. 初始化：
   • 创建一个与next数组长度相同的nextval数组。
   • nextval[0]初始化为-1，与next数组相同。
   • nextval[1]初始化为0，与next数组相同。
2. 计算 nextval 数组：
   • 从第二个字符开始，遍历模式串，计算每个位置的nextval值。
   • 对于每个位置i，首先根据next数组计算其前一个位置 i-1 的next值，即next[i]。
   • 检查在位置 i-1 的字符是否与位置next[i]的字符相同：
     • 如果相同，说明位置i的最长公共前后缀的下一个字符将会与位置i的字符重复比较，因此需要继续回溯，将nextval[i]设置为nextval[next[i]]。
     • 如果不同，说明位置i的最长公共前后缀的下一个字符与位置i的字符不同，可以直接使用next[i]作为nextval[i]。

算法实现

void get_nextval(SString T, int nextval[])
{int i, j;i = 1;j = 0;nextval[1] = 0;while (i < T.length){if (j == 0 || T.ch[i] == T.ch[j]){i++;j++;// 如果下一个字符与当前字符不同，则直接使用next[j]的值if (T.ch[i] != T.ch[j])nextval[i] = j;else// 如果下一个字符与当前字符相同，则继续回溯nextval[i] = nextval[j];}else{// 如果不匹配，则回溯到上一个next值j = nextval[j];}}
}