12.14字符串哈希

· · 个人记录

前情提要:
哈希,一种把字符串计算成一个值再映射到数组上还有概率出错的神奇算法。
思路大致是这样:选两个较大的质数(下称p和m)。再将字符串每一位的ascii码值乘上p,最终将会得到一个p进制数,在按位计算的过程中,每一步都要mod m,保证它不超出这个范围。最后的p进制数(用十进制表示)即为这个字符串的哈希值且不会超过m。

只要输入的字符串相同且使用的是同一种哈希算法,则它的哈希值一定会相同(但输入的字符串不同,也有可能出现哈希值相同的情况,这是小概率的哈希冲突)。
附上Code(P3370):

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
int n,cnt;
unsigned long long ans,p=131,mod=1e9+7,arr[10001];
string s;
void hashs(){
    cnt++;
    for(int i=0;i<s.length();i++) arr[cnt]=(s[i]+arr[cnt]*p%mod)%mod;
}
int main(){
    cin>>n;
    while(n--){
        cin>>s;
        hashs();
    }
    sort(arr+1,arr+1+cnt);
    for(int i=1;i<cnt;i++){
        if(arr[i]!=arr[i+1]) ans++;
    }
    ans++;
    cout<<ans;
    return 0;
}

T1
洛谷同题
Hash说完了，上STL！
看到的第一眼反应为set秒杀。
Code:

#include<iostream>
#include<string>
#include<set>
using namespace std;
int n;
set<string> g;
string s;
int main(){
    cin>>n;
    while(n--){
        cin>>s;
        g.insert(s);
    }
    cout<<g.size();
    return 0;
}

T2
洛谷同题
字符串长度太小了，不思考，O(n^4)暴力秒过。
Code:

#include<iostream>
#include<string>
#include<cstring>
using namespace std;
int ans,maxx;
string s1,s2;
int main(){
    cin>>s1>>s2;
    for(int i=0;i<s1.length();i++){
        for(int j=1;i+j<=s1.length();j++){
            string t=s1.substr(i,j);
            for(int k=0;k<s2.length();k++){
                for(int g=1;k+g<=s2.length();g++){
                    string x=s2.substr(k,g);
                    if(t==x) maxx=max(maxx,int(t.length()));
                }
            }
        }
    }
    cout<<maxx;
    return 0;
}

T5
洛谷同题
需要优化的map。
纯map会T掉最后一个点,因为把不存在的字符再遍历一遍太浪费时间了,所以要先用count函数确认一下,确定有这个字符串再扫。
Code:

#include<iostream>
#include<map>
#include<string>
using namespace std;
map<string,map<int,int>> ma;
int n,m;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        for(int j=1;j<=x;j++){
            string s;
            cin>>s;
            ma[s][i]=1;
        }
    }
    cin>>m;
    for(int i=1;i<=m;i++){
        string s;
        cin>>s;
        if(ma.count(s)!=0){
            for(int j=1;j<=n;j++){
                if(ma[s][j]==1) cout<<j<<" ";
            }
        }
        cout<<"\n";
    }
    return 0;
}