前：day5上午——字符串

衢州

T1 bzoj两个串

做通配符的匹配。
s[i] = t[m-1]

s[i]=t[1]
s[i+1]=t[2]
...
s[i+m-1]=t[m]

s[i]=t[-1]
s[i+1]=t[-2]
...
s[i+m-1]=t[-m]

s[i]=t[m-1]
s[i+1]=t[m-2]
...
s[i+m-1]=t[m-m]

s[i]=

bzoj两个串

T2 最小循环节

一个结论：如果(n-next[n])是n的因子，那么最小循环节长度就是这个，否则是n

相似的例题 poj2406

T3 NOI2014动物园

求多少个j，满足$s[1...j]=s[i-j+1...i]\ \ \ 1<=j<=i/2$
首先求出next数组，然后next，可能不满足j<=i/2的限制，可以沿着next往后跳，当满足i/2的限制后，加上现在next的个数。

UOJ35后缀排序

一个长度为n的字符串s
把s的所有后缀排序，求出每个后缀的排名和所有排名相邻后缀的最长公共前缀

JSOI2008 火星人

给一个字符串，支持插入与修改字符
询问两个后缀的LCP

POI2000病毒

建立AC自动机，