想起以前NOIP考试前死记硬背，然而并没有什么……
不如看邓公的课
字符串匹配很容易就能写出蛮力算法，即枚举主串中每个位置，把模式串放在这个位置，然后依次比对每一位，比对到不同的地方马上往后跳
运气好（数据随机、构成字符串的字符种类多），仅仅一次比对就可以发现错误，可是对于最坏情况就会浪费很多时间（如直到最后一个才成功），虽然这样的情况很少，导致期望水平都是线性，但某些条件下不好的情况还是多一些……比如DNA序列中只有四个字母，浪费时间的几率就会增加
因此需要把模式串快速移动到某个位置，使到匹配成功部分的某个前缀等于某个后缀，如上图第一行后缀与最后一行前缀
为了不漏掉中间的这种情况，需要保证匹配得最长
因此我们需要提前得到每一位前面的前缀等于后缀最长的长度
虽然可以暴力$\mathcal{O}(n^2)$得出，但是也可以用递推
设$F[i]$为字符串s第i位前面的最长公共真前缀真后缀（如果全等了就不移动，就没意义了），设F[0]=-1，那么$F[i+1]\leqslant F[i]+1$，当且仅当$s[F[i]]=s[i]$时取等号
当：显然，$s[F[i]]=s[i]$时$F[i+1]\leqslant F[i]+1$
仅当：反证，若这两个不等，$另一前缀x=另一后缀y+s[i]$，两边去掉最后一个字符得$另一前缀x-s[i]=另一后缀y$，由于$F[i]$是取最大值的，所以$F[i+1]\leqslant F[i]$，因此原式不取等号
从这两条可以得到$F[i+1]\leqslant F[i]+1$
若不等，可以找出F[F[i]]再判断，这样还是能保证当前前缀等于当前后缀，相当于次大的相等前缀后缀，当前缀后缀为空，则令F[i+1]为0
为了简化，设F[0]=-1，就可以不管空的情况，将两个统一
关于-1，假设s[-1]匹配所有字符即可
代码1
#define REP(r,x,y) for(register int r=x; r<y; r++) inline void getf(char *s) { int t=f[0]=-1; int l=strlen(s); REP(i,0,l) { while(t>=0 && s[i]!=s[t]) t=f[t]; // s[i]!=s[t] （t==-1匹配所有字符） t++; // f[i+1] = (f^x[i] + 1) until s[t]==s[i] f[i+1]=t; } }但是这个还有一点小问题
比如0000000000000，在某处失败后每次都只会向后移动一位，因为这处已经失败了，所以这一处不为0，所以后面移动都是多余的，因此我们需要快速移动到不等于当前位置的地方
由数学归纳法，从小到大只需要一次调整就可以保证不等
代码2
inline void getf(char *s) { int t=f[0]=-1; int l=strlen(s); REP(i,0,l) { while(t>=0 && s[i]!=s[t]) t=f[t]; t++; // f[i+1] = (fx[i] + 1) until s[t]==s[i] f[i+1]=(s[i]!=s[t]?t:f[t]); //induction…… } }但是这个时候$F$数组就不再表示最大前缀后缀了！
从上面看这个算法得到$F$数组需要$\mathcal{O}(n)$，再修改一下暴力查找算法就可以了
转载于:https://www.cnblogs.com/sahdsg/p/10865489.html
相关资源：JAVA上百实例源码以及开源项目