哈希

• 哈希理解起来就相当于用一种映射方式，以实现快速对比字符串或者其他东西(比如图)的功能，有时候利用技巧还能实现字典序大小的比较或者反映射操作。
• 其思想是非常重要而且容易理解的，关键在于hash方法以及编程上的技巧。
• 取一固定值\(P\)，把字符串看作\(P\)的进制数，代表每种字符。再取一固定值\(M\)，求出\(P\)进制位对\(M\)的余数，作为该字串的哈希值。
• 我们取\(P=233\)或\(P=13331\)，此时\(Hash\)值产生冲突的概率很低，只要\(Hash\)值相等，我们就可以认为原字符串是相等的。
• 我们通常取\(M=2^64\),即直接使用unsigned long long类型存储这个\(Hash值\)，这种类型自动对\(2^64\)取模，避免低效的mod运算。

实现方法

• 前缀和是hash的常见用法

方法一

#include <bits/stdc++.h>
using namespace std;
const int maxn=4e5+100;
const int base=233;
char s[maxn];
int poww[maxn],hash[maxn];
int main(){
    while(cin>>s+1){
        int len=strlen(s+1);
        poww[1]=233;
        for(int i=2;i<=len;i++)
            poww[i]=poww[i-1]*base;
        hash[1]=s[1];
        for(int i=2;i<=len;i++)
            hash[i]=hash[i-1]*base+s[i];
    }
}

方法二

• 把字符串变成数字

#define ull unsigned long long
ull gethash(string s){
    ull tmp=0;
    for(int i=0;i<s.size();i++)
        tmp=tmp*233+(s[i]-'a');
    return tmp;
}

一道例题

题目

已知字符串A与B，有n组询问，每次询问给l,r,s,t，要求O(1)判断A[l…r]与B[s…t]是否相同。

题解

• 既然已经求得两个字符串的hash数组，就直接取A[l..r]的哈希值与B[s…t]的哈希值进行比较即可。
• 那么如何更加方便的比较呢？
• 我们使用 \(hash[i]=hash[i-1]*10+s[i]\) 的方法进行哈希得哈希数组\(hasha,hashb\)。
• 然后我们发现一个问题:
  • 举一例子：

  \(s1: 1 2 3 4 5 1\)
  \(s2: 2 3 4 1 1 2\)

  • \(s1[2…4]\) 与 \(s2[1…3]\) 是相同的，但我们发现,\(hasha[4]-hasha[1]\)与\(hashb[3]-hashb[0]\)并不相同，为什么呢？
  • 回忆我们的哈希过程，发现我们要乘上一个 \(poww[i]\)，这样我们求出来的才是真正的哈希，即\(hash[r]-hash[l-1]*pow[i]\)

code

while(n--){
    cin>>l>>r>>s>>t;
    len=r-l+1;
    if(hasha[r]-hasha[l-1]*poww[len] == hashb[s]-hahsb[t-1]*poww[len])
        puts("YES");
    else puts("NO");
}

再来几道例题

manachar

普及知识

• 回文串：abcba(√),abba(√),abda(×)（就是正着看和倒着看相同的串）
• 子串≠子序列（子串是连续的，子序列可不连续）

一道例题

求一个字符串中最长回文子串长度。
例:字符串：abbababa   最长回文子串：ababa

题解

• manacher是一种暴力的优化，可以用O(n)的时间解决上述问题，但是我真的没怎么见过这玩意派上用场
• 可以学一下回文自动机，那个的作用要比这个大得多...
• 因为偶回文串比较难处理(不是以某个字符为中心)，所以首先我们要通过在每个相邻字符中间插入一个相同的字符（比如’|’，一定要是没有出现过的），这样预处理操作一发后我们会发现所有的回文串都是奇回文串，并且它也不会影响答案。
• 把预处理后的字符串叫做S
• 最后的出来的答案就是 S的最长回文子串长+1
• 复杂度O(n)也是容易理解的，因为R只有一次从1到n，以及i只有一次从1到n，而且二者是并列关系。
• 此种算法心中有印象即可，十分不常考。

code

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e8+100;
char a[maxn<<1];
int f[maxn<<1];
int main(){
    int cnt=0;a[0]='~';a[++cnt]='|'; char ch; int ans=0;
    while((ch=getchar())>='a' && ch<='z') a[++cnt]=ch,a[++cnt]='|';
    for(int i=1,r=0,mid=0;i<=cnt;i++){ //mid中心,i现在的点,f[]半径 
        if(i <= r) f[i]=min(f[mid*2-i],r-i+1);
        while(a[i-f[i]]==a[i+f[i]]) f[i]++;
        if(f[i]+i>r) r=f[i]+i-1,mid=i;
        if(f[i]>ans) ans=f[i];
    }
    printf("%d\n",ans-1);
    return 0;
}

推荐例题

有兴趣可以做一做洛谷板子题

KMP

讲解

• 详细讲解可参考本篇文章https://www.cnblogs.com/zhangtianq/p/5839909.html以及https://www.cnblogs.com/dusf/p/kmp.html此篇文章。

code

#include <bits/stdc++.h>
using namespace std;
const int maxn=1e6+100;
char a[maxn],b[maxn];
int fail[maxn];
int main(){
    cin>>a+1>>b+1;
    int lena=strlen(a+1),lenb=strlen(b+1);
    for(int i=2,j=0;i<=lenb;i++){
        while(j && b[i] != b[j+1]) j=fail[j];
        if(b[i] == b[j+1]) j++;
        fail[i]=j;
    }   
    for(int i=1,j=0;i<=lena;i++){
        while(j && a[i] != b[j+1]) j=fail[j];
        if(a[i] == b[j+1]) j++;
        if(j==lenb){
            cout<<i-lenb+1<<endl;
            j=fail[j];
        }
    }
    for(int i=1;i<=lenb;i++)
        cout<<fail[i]<<" ";

}

推荐题目：落谷板子题