Roc 语言 Dict.fold_until 深入解析：字典折叠的提前终止与全量累加
2026/9/20 12:49:26
话不多说，直接举例子展示：
1 模式串T：abaabc,求其失效函数
①首字符的f[ ]=-1，第二个字符的f[ ]=0（铁律）
| 下标 | 0 | 1 | 2 | 3 | 4 | 5 |
| 字符 | a | b | a | a | b | c |
| f[ ]/next | -1 | 0 |
②求T[2]的失效函数值，看其前一个字符b,f[1]=0，下标为0的字符是a，a和b不相等，无法往前走了，则用f[0]（失效函数值）+1，即0作为T[2]的失效函数值。
| 下标 | 0 | 1 | 2 | 3 | 4 | 5 |
| 字符 | a | b | a | a | b | c |
| f[ ]/next | -1 | 0 | 0 |
③求T[3]的的失效函数值，看其前一个字符a,f[2]=0，下标为0的字符是a，a和a相等，用0(下标值）+1，即1作为T[3]的失效函数值。
| 下标 | 0 | 1 | 2 | 3 | 4 | 5 |
| 字符 | a | b | a | a | b | c |
| f[ ]/next | -1 | 0 | 0 | 1 |
④求T[4]的失效函数值，看其前一个字符a,f[3]=1，下标为1的字符是b，b和a不相等，继续往前走，f[1]=0,下标为0的字符是a,a和a相等，用0(下标值）+1，即1作为T[4]的失效函数值。
| 下标 | 0 | 1 | 2 | 3 | 4 | 5 |
| 字符 | a | b | a | a | b | c |
| f[ ]/next | -1 | 0 | 0 | 1 | 1 |
⑤求T[5]的失效函数值，看其前一个字符b,f[4]=1,下标为1的字符是b,b和b相等，用1（下标值）+1，即2作为T[5]的失效函数值。
| 下标 | 0 | 1 | 2 | 3 | 4 | 5 |
| 字符 | a | b | a | a | b | c |
| f[ ]/next | -1 | 0 | 0 | 1 | 1 | 2 |
方法总结
①计算字符A的失效函数值，看其前面一个字符B，将B和下标为 B的失效函数值 的字符C作比较；
②如果B和C相等，则将C的下标+1作为A的失效函数值；
③若B和C不相等，继续向前，将B和下标为 C的失效函数值 的字符D作比较；
④若相等，则将D的下标+1作为A的失效函数值；（同②）
⑤若不相等继续向前，其实是在重复②-④步
⑥直至找到首字符Z仍然不相等，则将 Z的下标+1作为A的失效函数值（也就是-1+1=0）。
2 模式串：abcaabbabcabaacbacba,求其失效函数（附上答案，可以自查）
┏━━━━━━━━━┓
┃ 答 案 ┃
┗━━━━━━━━━┛
┏━━━━━━━━━┓
┃ 在 下 方
┗━━━━━━━━━┛
┏━━━━━━━━━┓
┃ 答 案 ┃
┗━━━━━━━━━┛
┏━━━━━━━━━┓
┃ 在 下 方
┗━━━━━━━━━┛
┏━━━━━━━━━┓
┃ 答 案 ┃
┗━━━━━━━━━┛
┏━━━━━━━━━┓
┃ 在 下 方
┗━━━━━━━━━┛
┏━━━━━━━━━┓
┃ 答 案 ┃
┗━━━━━━━━━┛
┏━━━━━━━━━┓
┃ 在 下 方
┗━━━━━━━━━┛
| 下标 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 |
字符 | a | b | c | a | a | b | b | a | b | c | a | b | a | a | c | b | a | c | b | a |
| f[] | -1 | 0 | 0 | 0 | 1 | 1 | 2 | 0 | 1 | 2 | 3 | 4 | 2 | 1 | 1 | 0 | 0 | 1 | 0 | 0 |
存档-KMP算法代码实现
haystack-匹配串，needle-模式串
class Solution { public: int strStr(string haystack, string needle) { //KMP算法 //先构造匹配串的next数组 if(needle.size()==0) return 0; vector<int> next(needle.size()); next[0]=0; for(int i=1,j=0;i<needle.size();i++){ while(j>0 &&needle[i]!=needle[j]){ j=next[j-1]; } if(needle[i]==needle[j]){ j++; } next[i]=j; } //匹配过程 for(int i=0,j=0;i<haystack.size();i++){ while(j>0 && haystack[i]!=needle[j]){ j=next[j-1]; } if(haystack[i]==needle[j]){ j++; } if(j==needle.size()){ return i-needle.size()+1; } } return -1; } };