abaaabb

bbaabba

0100011

1100110

如何O(1)判断两个字符串相等

一个想法是先转成2进制，再转成10进制，hash成整数值，O(1)比较

但是这个hash复杂度却是与串长同阶，类似于a*base^2+b

O(1)时间知道hash值就能O(1)比较两个字符串是否相等

baabc

b

ba

baa

baab

baabc

ba

记录前缀的hash值

1*3 ^3+0*3^2+

Hash[l~r]

Pre[x]=Pre[x-1]*26+(S[x]-‘a‘)

Pre[r]=Hash[l~r]

Pre[r] Pre[l-1]

Hash[l~r]

= Pre[r]-Pre[l-1]*26^(r-l)

abba

ab的hash

如何求后缀ba的hash

1*2^3+2*2^2+2*2^1+1*2^0

ab

1*2^1+2*2^0

让ab移位到和abba,*2^(r-l),移两位

这个幂次可以前缀乘O（n）预处理。。不要每次都算

然后让Hash["abba"]-Hash["ab"]

就能得到后缀"ba",的Hash值

由于int或者long long是自然溢出

出题人可能会卡这个模数。。就是两个不同的Hash值。。取模后相同了。。

区间相减。。有可能出现负数。。

然鹅。。-3mod10==7mod10,你-3mod10,本来应该是7，但是你算出来的这个-3可能与其他串hash值相同？

所以我们还是(a-b+mod)%mod,我们还可以用双hash..弄俩模数。。取模不相等才是合法的。。

abababaababacb

ababacb

kmp算法需要观察一个显然成立。。那就是匹配的串其前缀必定相等。。那么。。可能匹配的串其前缀

nxt[]数组：求一个前缀与后缀匹配。。请求出最长的前缀长度。。输出长度和char答案

一个显然的事实：长度为len的前缀和后缀分别只有一个

另一个显然的事实：每一个后缀都是不同的

nxt[]数组求得是除了以i结尾的串的，最长的前缀的长度。。但是这个前缀长度我们一般不会扩展到以i结尾，即1~i的长度（串从1开始）

ababac T

nxt[1]=0;是一个显然的事实

nxt[4]=2

nxt[5]=3

nxt[4]的前缀后面加一格是nxt[5]所考虑的前缀。。nxt[4]的后缀加一格是nxt[5]所考虑的后缀

n/1+n/2+n/3+......+n/n==>nlogn

周期串满足的性质：

字符串知识储备