字符串哈希
哈希是什么？
- 把一个串或者字符映射成一串数字，再通过取模的方式来使其可以被存下
字符串哈希？
- 把字符串用数字的方式写出
具体的，我们可以通过把字符串变成一个k进制数，最后通过取余实现
P3370 【模板】字符串哈希
#include<bits/stdc++.h>
#define int long long
#define mod 111111111
using namespace std;
const int base=131;
string s;
int n;
int p[1000010];
map<int,bool>haash;
int sum[100010];
signed main(){
cin>>n;
int ssum=0;
for(int i=1;i<=n;i++){
cin>>s;
int len=s.size();
int ans=0;
for(int j=0;j<len;j++){
ans=(ans*base+(int)s[j])%mod;
}
if(haash[ans])
ssum++;
haash[ans]=1;
}
cout<<n-ssum;
return 0;
}
前缀哈希：
- 通过前缀和加哈希值的方式，再通过前缀和加减的方式求区间哈希值
- 有进制限制怎么来求
- 前面的乘上长度进制
for(int i=1;i<=n;i++){
p[i]=p[i-1]*base;
p[i]%=mod;
pre[i]=(pre[i-1]*base+s[i])%mod;
}
int get_hash(int l,int r){
return ((pre[r]-pre[l-1]*p[r-l+1]%mod)%mod+mod)%mod;
}
P3501 [POI2010] ANT-Antisymmetry
- 看到这题要求子串相同，考虑用字符串哈希
- 子串考虑前缀哈希，因为要取反，考虑用两个数组，一个是取反前的，一个是取反后的，然后发现长度又单调性，可以二分，只有当前满足，更小的一定有。
- 所以加上长度，是满足要求的个数
#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
using namespace std;
const int base=131;
string s;
int len;
ull pre[500010],suf[500100],p[500010];
void init(){
p[0]=1;
for(int i=1;i<=len;i++){
p[i]=p[i-1]*base;
pre[i]=pre[i-1]*base+(s[i]-'0'+31);
}
for(int i=len;i>=1;i--){
suf[i]=suf[i+1]*base+('1'-s[i]+31);
}
}
ull get_hash(int l,int r){
if(l==0) return 0;
return pre[r]-pre[l-1]*p[r-l+1];
}
ull get_suf(int l,int r){
if(l==0) return 0;
return suf[l]-suf[r+1]*p[r-l+1];
}
signed main(){
ios::sync_with_stdio(false);
cin>>len;
cin>>s;s=" "+s;
init();
int ret=0;
for(int i=1;i<len;i++){
int l=0,r=(i,len-i),ans=0;
while(l<=r){
int mid=l+r>>1;
if(get_hash(i-mid,i)==get_suf(i+1,i+1+mid)){
l=mid+1;ans=l;
}
else r=mid-1;
}
ret+=ans;
}
cout<<ret;
return 0;
}
P3498 [POI2010] KOR-Beads
- 读题发现这题有子串，还需要比较是否相同，发现可以用前缀后缀哈希
- 发现可以枚举长度，然后再枚举每一个串，再做前缀和后缀和
- 比较是否被标记
#include<bits/stdc++.h>
#define ll long long
#define ull long long
using namespace std;
ull base=11451411;
const int N=2e5+20;
int n,a[N];
ull p[N],h1[N],answer[N],h2[N];
char s[N];
ull hash1(int r,int l){
return (h1[r]-h1[l-1]*p[r-l+1]);
}
ull hash2(int r,int l){
return (h2[l]-h2[r+1]*p[r-l+1]);
}
map<ull,bool>q;
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
p[0]=1;
for(int i=1;i<=n;i++){
p[i]=p[i-1]*base;
h1[i]=(h1[i-1]*base+a[i]);
}
for(int i=n;i>=1;i--){
h2[i]=h2[i+1]*base+a[i];
}
int ans=0,cnt=0;
for(int k=1;n/k>=ans;k++){
int sum=0;
for(int i=k;i<=n;i+=k){
int dw1=hash1(i,i-k+1);
int dw2=hash2(i,i-k+1);
if(q[dw1]==0&&q[dw2]==0){
q[dw1]=1,q[dw2]=1;
sum++;
}
}
if(ans<sum){
ans=sum;
cnt=0;
answer[++cnt]=k;
}
else if(ans==sum){
answer[++cnt]=k;
}
q.clear();
}
cout<<ans<<" "<<cnt<<endl;
for(int i=1;i<=cnt;i++){
cout<<answer[i]<<" ";
}
return 0;
}
相似的回忆
- 小 D 和小 Y 是一起长大的好朋友。在他们的童年里，有许多相似的回忆。现在，小 D 和小 Y 已不再年轻，他们回想起过去的时光，希望你能帮他们找出这些相似的回忆。
我们把一个人的回忆，看做一个字符串 \(S[1…|S|]\) ，其中 \(|S|\) ，表示字符串的长度，\(S_i(1≤i≤|S|)\) 表示字符串第 \(i\) 位上的字符。
对于两段回忆 \(S[1…|S|]\) , \(T[1…|T|]\) ，我们认为它们是相似的，当且仅当满足如下两个条件：|S|=|T|。对于所有二元组 \((i,j)(1≤i≤j≤|S|)\)
- 若 \(S_i=S_j ，则 T_i=T_j\)
- 若 \(S_i≠S_j ，则 T_i≠T_j\)
。
现在，小 D 把他的所有回忆 \(a[1…|a|]\) ,告诉了你，而小 Y 则给了你一个回忆片段 \(b[1…|b|]\) 。保证 \(|a|≥|b|\) 。请你求出，\(a\) 中有多少子串与 \(b\) 是相似的。
我们称一个串是另一个串的子串，当且仅当前者能通过从后者的开头、结尾各删除若干字符（可以为 \(0\) ，即不删）得到。
另外，由于小 D 和小 Y 的回忆非常丰富，不足以用有限的英文字母表示出来，所以我们用数字来表示这些串。每个数字代表串的一位。数字间用空格隔开。
输出一行一个非负整数，表示 \(a\) 中有多少子串与 \(b\) 是相似的。
- 看到这一题最暴力的做法就是把每一个的相同的上一个找出来，看与他的位置的距离是多远，最后比较一下
#include<bits/stdc++.h>
using namespace std;
int n,m;
int a[200010],b[200010],pre1[2000010],pre2[2000100];
map<int,int>mp;
signed main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
if(!mp[a[i]]){
pre1[i]=0;
mp[a[i]]=i;
}
else{
pre1[i]=mp[a[i]];
mp[a[i]]=i;
}
}
mp.clear();
for(int i=1;i<=m;i++){
cin>>b[i];
if(!mp[b[i]]){
pre2[i]=0;
mp[b[i]]=i;
}
else{
pre2[i]=mp[b[i]];
mp[b[i]]=i;
}
}
int ans=0;
for(int i=1;i<=n-m+1;i++){
bool flag=0;
for(int j=i;j<=m+i-1;j++){
if((pre1[j]-i+1)*(pre1[j]>=i)!=pre2[j-i+1]){
flag=1;
break;
}
}
if(!flag) ++ans;
}
cout<<ans;
return 0;
}
- 考虑优化一下，发现每过一个区间，至多有一个会发生变化