POJ3690 Constellations
sdxjzsq
2020-03-10 03:04:07
### 背景
作为[字符串算法](https://www.luogu.com.cn/blog/xjzsq/zi-fu-chuan-suan-fa)中二维字符串哈希的一个例题。因题解较长，故单独成文。
### 题目链接
http://poj.org/problem?id=3690
### 题意
求$t$个$p\times q$矩阵有几个在$n\times m$的字符矩阵（01矩阵）中出现。
### 思路
##### 最终算法：二维字符串哈希+multiset优化
首先使用二维字符串哈希算法计算出天空中所有大小为$p\times q$的子矩阵的哈希值和$t$个大小为$p\times q$的星座矩阵的哈希值，并把$t$个星座的的哈希值存到`multiset`中，然后尝试将$(n-p+1)\times(m-q+1)$个子矩阵的哈希值从multiset里面删除，最后$t$与multiset大小的差即是答案。
##### 题目历程：TLE\*n->RE\*n->TLE->AC
考虑把矩阵拆开一行一行比较，然后写个简单的hash，结果TLE
之后学习了一下二维字符串哈希，按照上面的写法依然TLE
经过研究发现，因为是已经固定住需要计算的子矩阵大小，因此可以直接预处理出具体值，而不是用到的时候再使用差分计算结果。而一直TLE的原因也是因为差分的时候浪费了时间，与是否用二维字符串哈希没有太大关系。甚至如果使用不加优化的二维字符串哈希，速度甚至更慢（一维:1875ms->二维:2157ms）
这个题目告诉我们，没有万能的模板，还需要具体情况具体分析，做一些贴合题目的优化，不能生搬硬套。
但是，之前找题解的时候，看到使用二维字符串hash的题解可以跑到766ms,就算是我的常数大，也不至于这么...经过研读代码发现，它使用了[`multiset`](https://www.luogu.com.cn/blog/xjzsq/stl-xiang-guan)来存$t$个$p\times q$矩阵的哈希值，然后尝试将$(n-p+1)\times(m-q+1)$个子矩阵的哈希值从multiset里面删除，最后$t$与multiset大小的差即是答案，于是产生了第二个版本的代码。
然而......写完上面这些文字以后，@[ketchuppp](https://ketchuppp.xyz/)在网上又找到了[一个题解](https://www.cnblogs.com/luyouqi233/p/8010951.html)，竟然直接就是二维字符串哈希的板子+multiset优化，而且提交了一下发现，**跑 得 更 快**，真是**震 撼 我 妈 一 整 年**!!!果断把之前T掉的直接套二维板子的代码用multiset优化了下，结果跑出了最快的907ms，这是真的玄学......有没有哪位老板可以解释一下这个情况（情况如下，物极必反...？？）？
|运行时间|无优化|multiset优化|
|:--:|:-:|:-:|
|二维字符串哈希板子|$>3000ms(TLE)$|$907ms$|
|某另类玄学预处理|$2105ms$|$1075ms$|
### code（按照AC顺序排列）
一维字符串哈希：(1875ms)
``` cpp
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn = 1005,base = 233;
unsigned long long n,m,t,p,q,h[maxn][maxn],hh[maxn],p1,top,ans;
char s[maxn][maxn];
inline unsigned long long power(unsigned long long x,unsigned long long k)
{
unsigned long long ansx=1;
while(k>0)
{
if(k&1)ansx=ansx*x;
x=x*x;
k>>=1;
}
return ansx;
}
inline bool check(int i,int j)
{
for(register int k=1;k<=p;k++)
if(hh[k]!=h[i+k-1][j])
return false;
return true;
}
int main()
{
while(1)
{
ans=0;
scanf("%llu%llu%llu%llu%llu",&n,&m,&t,&p,&q);
if(n==0)return 0;
memset(h,0,sizeof(h));
p1=power(base,q-1);
for(register int i=1;i<=n;i++)
{
scanf("%s",s[i]+1);
for(register int j=1;j<=q;j++)h[i][1]=h[i][1]*base+(s[i][j]=='*'?1:0);
for(register int j=2;j<=m-q+1;j++)h[i][j]=(h[i][j-1]-(s[i][j-1]=='*'?p1:0))*base+(s[i][j+q-1]=='*'?1:0);
}
while(t--)
{
memset(hh,0,sizeof(hh));
for(register int i=1;i<=p;i++)
{
scanf("%s",s[i]+1);
for(register int j=1;j<=q;j++)hh[i]=hh[i]*base+(s[i][j]=='*'?1:0);
}
bool flag = false;
for(register int i=1;i+p-1<=n;i++)
{
for(register int j=1;j+q-1<=m;j++)
if(check(i,j))
{
ans++;
flag=true;
break;
}
if(flag)break;
}
}
printf("Case %llu: %llu\n",++top,ans);
}
return 0;
}
```
二维字符串哈希+multiset优化：(1075ms)
```cpp
#include<cstdio>
#include<cstring>
#include<set>
using namespace std;
const int maxn = 1005,base = 233,base2 = 666;
unsigned long long n,m,t,p,q,h[maxn][maxn],h2[maxn][maxn],hh[maxn],hh2,p1,p2,top,ans;
char s[maxn][maxn];
inline unsigned long long power(unsigned long long x,unsigned long long k)
{
unsigned long long ansx=1;
while(k>0)
{
if(k&1)ansx=ansx*x;
x=x*x;
k>>=1;
}
return ansx;
}
int main()
{
while(1)
{
ans=0;
scanf("%llu%llu%llu%llu%llu",&n,&m,&t,&p,&q);
if(n==0)return 0;
memset(h,0,sizeof(h));
memset(h2,0,sizeof(h));
p1=power(base,q-1);
p2=power(base2,p-1);
for(register int i=1;i<=n;i++)
{
scanf("%s",s[i]+1);
for(register int j=1;j<=q;j++)h[i][1]=h[i][1]*base+(s[i][j]=='*'?1:0);
for(register int j=2;j<=m-q+1;j++)h[i][j]=(h[i][j-1]-(s[i][j-1]=='*'?p1:0))*base+(s[i][j+q-1]=='*'?1:0);
}
for(register int j=1;j<=m-q+1;j++)
{
for(register int i=1;i<=p;i++)h2[1][j]=h2[1][j]*base2+h[i][j];
for(register int i=2;i<=n-p+1;i++)h2[i][j]=(h2[i-1][j]-h[i-1][j]*p2)*base2+h[i+p-1][j];
}
ans=t;
multiset<unsigned long long> S;
while(t--)
{
memset(hh,0,sizeof(hh));hh2=0;
for(register int i=1;i<=p;i++)
{
scanf("%s",s[i]+1);
for(register int j=1;j<=q;j++)hh[i]=hh[i]*base+(s[i][j]=='*'?1:0);
hh2=hh2*base2+hh[i];
}
S.insert(hh2);
}
for(register int i=1;i<=n-p+1;i++)
for(register int j=1;j<=m-q+1;j++)
S.erase(h2[i][j]);
printf("Case %llu: %llu\n",++top,ans-(unsigned long long)S.size());
}
return 0;
}
```
二维字符串哈希板子+multiset优化：(907ms)
``` cpp
#include<cstdio>
#include<cstring>
#include<set>
using namespace std;
const int maxn= 1005,base1=235,base2=666,mod = 19491001;
unsigned long long n,m,t,p,q,top,h[maxn][maxn],h2[maxn][maxn],hh[maxn],p1,p2,ans;
char s[maxn][maxn];
inline unsigned long long power(unsigned long long x,unsigned long long k)
{
unsigned long long ansx=1;
while(k>0)
{
if(k&1)ansx=ansx*x;
x=x*x;
k>>=1;
}
return ansx;
}
inline unsigned long long get_hash(unsigned long long x,unsigned long long y)
{
return h2[x+p-1][y+q-1]-h2[x+p-1][y-1]*p1-h2[x-1][y+q-1]*p2+h2[x-1][y-1]*p1*p2;
}
int main()
{
while(scanf("%llu%llu%llu%llu%llu",&n,&m,&t,&p,&q)!=EOF)
{
multiset<unsigned long long> S;
if(n==0)return 0;
p1=power(base1,q);
p2=power(base2,p);
for(register int i=1;i<=n;i++)
{
scanf("%s",&s[i]);
for(register int j=1;j<=m;j++)h[i][j]=h[i][j-1]*base1+(s[i][j-1]=='*'?1:0);
}
for(register int j=1;j<=m;j++)
for(register int i=1;i<=n;i++)
h2[i][j]=h2[i-1][j]*base2+h[i][j];
ans = t;
while(t--)
{
memset(hh,0,sizeof(hh));
for(register int i=1;i<=p;i++)
{
scanf("%s",&s[i]);
for(register int j=1;j<=q;j++)hh[i]=hh[i]*base1+(s[i][j-1]=='*'?1:0);
}
for(register int i=1;i<=p;i++)hh[0]=hh[0]*base2+hh[i];
S.insert(hh[0]);
}
for(register int i=1;i<=n-p+1;i++)
for(register int j=1;j<=m-q+1;j++)
S.erase(get_hash(i,j));
printf("Case %llu: %llu\n",++top,ans-S.size());
}
return 0;
}
```