CF958A2 Death Stars (medium) 题解

· · 题解

字符串哈希板子题。考虑如何将 A 的一个 m\times m 的子矩阵匹配到 B 中一个完全相等的，想到哈希，对于 A 中所有子矩阵进行编码，用一个 std::map 存储，对于 B 的每一个子矩阵在 map 中扫一遍，如果它的哈希值出现过就直接输出答案。

这里用的单模哈希，选的模数为 10^9+9，Base（进制数）为 6803，足以通过。

放代码：

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+9,base=6803;
map<int,int> p;
main(){
  ios::sync_with_stdio(false);
  int n,m; cin>>n>>m;
  vector<string> a(n),b(m);
  for(auto &i:a)cin>>i;
  for(auto &i:b)cin>>i;
  for(int i=0;i<=n-m;i++){
    int c=0;
    for(int j=i;j<i+m;j++)
      for(char k:a[j])c=(c*base+k-96)%mod;
    p[c]=i+1; // 将哈希值存入 map
  }
  for(int i=0;i<=n-m;i++){
    int c=0;
    for(int j=0;j<m;j++)
      for(int k=i;k<i+m;k++)
        c=(c*base+b[j][k]-96)%mod;
    if(p[c]){ // 该值存在
      cout<<p[c]<<' '<<i+1<<endl; break;
    }
  }
  return 0;
}