CVBB ACM Team 2020-2021:teams:farmer_john:2sozx:字符串

2020-2021:teams:farmer_john:2sozx:字符串:扩展kmp

Anonymous (anonymous@undisclosed.example.com) — 2020-05-23T15:07:39+0800

扩展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]…

2020-2021:teams:farmer_john:2sozx:字符串:kmp

Anonymous (anonymous@undisclosed.example.com) — 2020-05-22T10:26:00+0800

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; }

2020-2021:teams:farmer_john:2sozx:字符串:manacher

Anonymous (anonymous@undisclosed.example.com) — 2020-05-22T10:40:07+0800

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; }

2020-2021:teams:farmer_john:2sozx:字符串:shift_and

Anonymous (anonymous@undisclosed.example.com) — 2020-05-08T15:21:38+0800

Shift-and * 挺好的讲解 * 还不太熟悉