2020-2021:teams:farmer_john:2sozx:字符串:kmp
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 | |||
|
2020-2021:teams:farmer_john:2sozx:字符串:kmp [2020/05/22 10:21] 2sozx |
2020-2021:teams:farmer_john:2sozx:字符串:kmp [2020/05/22 10:26] (当前版本) 2sozx |
||
|---|---|---|---|
| 行 2: | 行 2: | ||
| ====简介==== | ====简介==== | ||
| 本质上是 $nxt$ 数组，$nxt[j]=k$ 表示 $j$ 之前的字符串中有最大长度为 $k$ 的相同前缀后缀。 | 本质上是 $nxt$ 数组，$nxt[j]=k$ 表示 $j$ 之前的字符串中有最大长度为 $k$ 的相同前缀后缀。 | ||
| + | ====代码==== | ||
| + | <code cpp> | ||
| + | nxt[1]=0; | ||
| + | for(i=2;i<=n;i++){ | ||
| + | while(j&&ch[j+1]!=ch[i]) j=nxt[j]; | ||
| + | if(ch[j+1]==ch[i]) j++; | ||
| + | nxt[i]=j; | ||
| + | } | ||
| + | </code> | ||
2020-2021/teams/farmer_john/2sozx/字符串/kmp.1590114086.txt.gz · 最后更改: 2020/05/22 10:21 由 2sozx
