https://wiki.cvbbacm.com/ 2026-04-30T05:19:35+0800 https://wiki.cvbbacm.com/ https://wiki.cvbbacm.com/lib/exe/fetch.php?media=favicon.ico text/html 2020-05-23T15:07:39+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:farmer_john:2sozx:%E5%AD%97%E7%AC%A6%E4%B8%B2:%E6%89%A9%E5%B1%95kmp&rev=1590217659&do=diff 扩展kmp 简介 定义母串 $S$，和字串 $T$，设 $S$ 的长度为 $n，T$ 的长度为 $m$ ，求 $T$ 与 $S$ 的每一个后缀的最长公共前缀，也就是说，设 $extend$ 数组, $extend[i]$ 表示 $T$ 与 $S[i,n-1]$ 的最长公共前缀，要求出所有 $extend[i](1\le i\le n)$。 代码 l1=strlen(a+1),l2=strlen(b+1); nxt[1]=l2; i=1; while(b[i]==b[i+1]&&i+1<=l2) i++; nxt[2]=i-1; pos=2; for(i=3;i<=l2;i++){ if(pos+nxt[pos]>=i) nxt[i]=min(nxt[i-pos+1],pos+nxt[pos]-i); while(b[nxt[i]+1]==b[nxt[i]+i]) nxt[i]++; if(nxt[i]+i>pos+nxt[pos]) pos=i; } pos=1; int l=min(l1,l2); for(i=1;i<=l;i++) { if(a[i]!=b[i]… text/html 2020-05-22T10:26:00+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:farmer_john:2sozx:%E5%AD%97%E7%AC%A6%E4%B8%B2:kmp&rev=1590114360&do=diff KMP 简介 本质上是 $nxt$ 数组，$nxt[j]=k$ 表示 $j$ 之前的字符串中有最大长度为 $k$ 的相同前缀后缀。 代码 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; } text/html 2020-05-22T10:40:07+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:farmer_john:2sozx:%E5%AD%97%E7%AC%A6%E4%B8%B2:manacher&rev=1590115207&do=diff Manacher 代码 pat[0]='@'; for(i=1;i<=n;i++) pat[2*i-1]=ch[i],pat[2*i]='@'; pos=0,r[0]=0; for(i=1;i<=2*n;i++){ if(i<=pos+r[pos]) r[i]=min(pos+r[pos]-i,r[pos*2-i]); while(i>r[i]&&pat[i+r[i]+1]==pat[i-r[i]-1]) r[i]++; if(i+r[i]>pos+r[pos]) pos=i; } text/html 2020-05-08T15:21:38+0800 Anonymous (anonymous@undisclosed.example.com) https://wiki.cvbbacm.com/doku.php?id=2020-2021:teams:farmer_john:2sozx:%E5%AD%97%E7%AC%A6%E4%B8%B2:shift_and&rev=1588922498&do=diff Shift-and * 挺好的讲解 * 还不太熟悉