题意：给一个字符串，求出其border长度（前缀=后缀，且长度最长），然后切掉第一个和最后一个字母，再求border，直到字符串切么得了。
题解：
首先要发现一个性质：设一个字符串的border长度为x，那么，在这个字符串头尾各加上一个字母，新字符串的border长度最多为x+2。
证明的话，考虑反证法：设原串border长度为x，即长度最长的前缀=后缀，假设添加字母之后，border'>x+2,那么把长度=border'的前缀平移到长度=border'的后缀上一比对，容易看出原串border长度>x，产生矛盾。
那么考虑题目所说的这个过程的反过程，就是每次添加字母，每次的添加，最多使得border+2，那么总共最多使得border增加2*n/2=O(n)，然后考虑减少的，即，原串border=x，新串border'<x+2，设delta=border-border'，发现这个delta总共也是O(n)的（废话，增加的总共O(n)，减少的肯定也是O(n)），那么。。直接hash+暴力不就行了吗。。这样总共的check次数是O(2n)的。
注意hash姿势。。出题人精心卡掉了自然溢出的hash姿势。存在另外一种hash姿势：选择一个小质数和一个大质数，小质数作为hash的进制数字，大质数用作取模，并采取多重hash防止冲突。。。总之被卡的已经不省人事了。。主要写博客为了记录下这种hash姿势以及hash质数。。。下次被卡了就拜一下这个题。。
Code：
#include<bits/stdc++.h> using namespace std; const int maxn = 1e6+100; const int HASH_NUM = 10; typedef long long LL; int AC[HASH_NUM] ={131,137,139,149,151,157,163,167,173,179}; int ACC[HASH_NUM] ={200003,200009,200017,200023,200029,200033,200041,200063,200087,200117}; LL bas[maxn][HASH_NUM]; int n; char s[maxn]; LL sum1[maxn][HASH_NUM]; int ans[maxn]; bool check(int index,int x,int len){ LL hs1 = ((sum1[x+len-1][index]-sum1[x-1][index]*bas[len][index]