背景

作为字符串算法中二维字符串哈希的一个例题。因题解较长，故单独成文。

题目链接

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来存$t$个$p\times q$矩阵的哈希值，然后尝试将$(n-p+1)\times(m-q+1)$个子矩阵的哈希值从multiset里面删除，最后$t$与multiset大小的差即是答案，于是产生了第二个版本的代码。
然而......写完上面这些文字以后，@ketchuppp在网上又找到了一个题解，竟然直接就是二维字符串哈希的板子+multiset优化，而且提交了一下发现，跑 得 更 快，真是震 撼 我 妈 一 整 年!!!果断把之前T掉的直接套二维板子的代码用multiset优化了下，结果跑出了最快的907ms，这是真的玄学......有没有哪位老板可以解释一下这个情况（情况如下，物极必反...？？）？

code（按照AC顺序排列）

一维字符串哈希：(1875ms)

#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)

#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)

#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;
}