字符串算法入门笔记
zhx：什么AC自动机，KMP算法从来不会考
zhx：不推荐用 string，因为麻烦
读ans入一个字符串
char s[MAXN];
cin>>s+1;//从s[1]开始读入，操作时方便
在遍历字符串时，我们要先把字符串长度存下来，因为计算字符串长度的函数 strlen 的时间复杂度为\(O(长度)\)，如果写成
for(int i=1;i<=strlen(s+1);i++)
就很容易TLE;
因此
int len=strlen(s+1);
for(int i=1;i<=len;i++)
比较字符串：
朴素想法：我们把每个字符串的每一位都进行比较，设字符串长度为 \(k\)，比较一次的复杂度为 \(O(k)\)。
当有很多字符串的时候时间复杂度会很大,所以我们用一个神奇的字符串算法 字符串哈希。
字符串 -> 数
如：abc -> 123
问题 哈希碰撞：
例如：
ka -> 111
aaa-> 111
我们发现明明这两个字符串不一样，但他们的hash值是一样的，这时就发生了哈希碰撞。
单模哈希法
用 \(27\) 进制（别的其实也可以）存储下来字符串。但是由于数太大了，所以我们定义一个 \(p\) 用来取模。但是有可能存在取模后数字一样的情况，为了使碰撞的概率尽可能小， \(p\) 必须是奇数，尽量为质数，而且要增大，这里选用 \(10^9+7\)。
双模哈希法
就是要模两次，不常用，略。
自然溢出法（不模哈希法）
让他自己爆掉 unsigned long long,让其自然取模，时间复杂度很低。
所以应该用自然溢出法。
时间排序：双模>单模>不模
哈希碰撞率：不模>单模>双模