终于开始学习新的东西了，总结一下字符串的一些知识。
NO.1 字符串哈希（Hash） 定义即将一个字符串转化成一个整数，并保证字符串不同,得到的哈希值不同，这样就可以用来判断一个该字串是否重复出现过。
所以说\(Hash\)就是用来求字符串是否相同或者包含的。（包含关系就可以枚举区间，但是通常用\(KMP\)，不会真的有人用看脸的\(Hash\)做字符串匹配吧，不会吧不会吧)。
实现实现方式也是比较简单的，其实就是把一个字符串转化为数字进行比较，到这里可能有人就会说，直接比较长度和\(ASCII\)码不就行了，也是转化成数字啊（放屁）。这样显然是不行的，就好比说"ab"和“ba“，这两个显然不一样，但是如果按上边说的进行比较就是一样的，这样就错了，所以我们要换一种方式：改变一下进制。
如果是一个纯字符串的话，那么我们应该把进制调到大于\(131\)，因为如果小于，就不能给每一种的字符一个值，那么正确性也就无法保证了。所以取一个\(233\)，合情合理，还很sao（逃。因为这个值至少能保证不会炸。我们求出来每个字符串对应的数字，然后进行比较就好了。
对于哈希而言，我们认为对一个数取模后一样，那么就是一样的，所以可以偷点懒，也就是自然溢出，使用\(unsigned\ long\ long\)，相当于自动对\(2^{64}\)取模，然后进行比较即可，当然，可以自己背一个\(10^{18}\)的质数进行取模（毕竟也是能卡的，也不知道哪个毒瘤会卡），各有优缺点。
代码 ull Hash(char s[]){//ull自然溢出 ull res = 0; int len = strlen(s); for(int i=0;i<len;++i){//计算每一位，用自己定义的进制base乘（也就是233 qwq） res = (res*base + (ull)s[i])%mod;//这里我是取了个玄学mod } return res; }以上就是整个字符串之间的对比。下边说一说字符串里某个区间的对比
区间对比意思就是直接给出你几个字符串，对比每个字符串里给定的区间\([l,r]\)，这样的话如果直接一个个的扫，肯定会慢好多，如果直接求整个串然后相减，那么肯定是错误的，因为每一位都是要乘以一个进制的，如果直接计算，那么肯定就会乱掉，也就\(WA\)了。所以要用到之前说的东东：前缀和。
我们记录每一位的前缀和，而记算的时候需要乘以当前位的进制，这样就会避免上边说到的那种迷惑错误。记录的时候就照常按照前缀和记录，只需要最后改一下判断就行。
定义\(pw[len]\)为长度为\(len\)时的需要乘以的进制，前缀和就用\(sum\)来表示，求前缀和就是这样：
int main(){ cin>>s; int len = strlen(s); sum[0] = (ull)s[0]; for(int i=1;i<len;++i){ sum[i] = sum[i-1]*base+(ull)a[i];//乘以进制不能忘 } }下边是判断是否合法：
while(n--){ int l,r,s,t,len; cin>>l>>r>>s>>t; len = r-l+1;//计算第几位来乘以进制，pw数组提前可以快速幂处理好 if(sum[r] - sum[l-1]*pw[len] == sum[t]-sum[s-1]*pw[len])printf("YES\n");//如果这样计算出来值相等就合法 else printf("NO\n"); } 模板例题字符串哈希
例题代码 #include<bits/stdc++.h> using namespace std; #define ull unsigned long long const ull mod = 1926081719260817; const int maxn = 1e4+10; ull base = 233; int a[maxn]; char s[maxn]; ull Hash(char s[]){ ull res = 0; int len = strlen(s); for(int i=0;i<len;++i){ res = (res*base + (ull)s[i])%mod; } return res; } int main(){ int n; scanf("%d",&n); for(int i=1;i<=n;++i){ cin>>s; a[i] = Hash(s); } int ans = 1; sort(a+1,a+n+1); for(int i=1;i<n;++i){ if(a[i] != a[i+1])ans++; } printf("%d\n",ans); } NO.2 Manacher算法学长说很不常用，所以理解一个思想即可。
定义\(1975\)年，\(Manacher\)发明了\(Manacher\)算法（中文名：马拉车算法），是一个可以在\(O(n)\)的复杂度中返回字符串\(s\)中最长回文子串长度的算法，十分巧妙。
例如这个字符串：“abaca”，它可以处理每一位的回文字串，以\(O(n)\)的效率处理最大值（当然还是有扩展的，只不过它不太常用，就只是分析一下算法过程）
因为回文串分为奇回文串和偶回文串，处理起来比较麻烦，所以我们要用到一个小（sao）技（cao）巧（zuo），在每两个字符之间插入一个不会出现的字符，但是要求插入的字符一样，这样才能保证不影响回文串的长度。
举个例子：“abbadcacda”这个字符串，我们需要插入新的字符，这里用’#'，那么就有了如下对应关系：