1170: [Balkan2007]Cipher

1170: [Balkan2007]Cipher

给出一个字符矩阵,你要从中找出一个出现次数最多的子矩阵.

毒瘤，真的毒瘤。

数据范围在一千，想了一下应该是hash，方法很简单，选定两个base，一个从上到下，另一个从左到右。

hash[i][j]=hash[i-1][j]*base2+hash[i][j-1]*base1-hash[i-1][j-1]*base1*base2+((int)ch[i][j]+1);

加上上方和左侧的矩阵再减去重复的部分，计算hash时也与此相同。

然后就是细节了。

下面给出代码：

#include<iostream>
#include<cstring>
#include<string>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;
inline unsigned long long rd(){unsigned long long x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-1;for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';return x*f;
}
inline void write(int x){if(x<0) putchar('-'),x=-x;if(x>9) write(x/10);putchar(x%10+'0');return ;
}
int n,m,a,b;
char ch[1006][1006];
unsigned long long hash[1006][1006],base1=1000000003,base2=1000000007,s[1000006],p1[10006],p2[10006];//其实可以用int 
int main(){p1[0]=1,p2[0]=1;n=rd(),m=rd();for(int i=1;i<=m;i++) p1[i]=p1[i-1]*base1;//将base的次方预处理 for(int i=1;i<=n;i++) p2[i]=p2[i-1]*base2;//important，这里的m,n千万不能写反，否则会出现需要的次方为零的情况 （被坑了好久QAQ） for(int i=1;i<=n;i++){gets(ch[i]+1);for(int j=1;j<=m;j++){hash[i][j]=hash[i-1][j]*base2+hash[i][j-1]*base1-hash[i-1][j-1]*base1*base2+((unsigned long long)ch[i][j]+1);//预处理hash 
        }}a=rd(),b=rd();int cnt=0;for(int i=a;i<=n;i++){for(int j=b;j<=m;j++){s[++cnt]=hash[i][j]+hash[i-a][j-b]*p2[a]*p1[b]-hash[i-a][j]*p2[a]-hash[i][j-b]*p1[b];//记录所有大小为xy的矩阵的hash值 
        }}sort(s+1,s+cnt+1);int ans=0,h=0;unsigned long long num=0;cout<<a<<" "<<b<<endl;for(int i=1;i<=cnt;i++){//找出现最多的 if(s[i]!=s[i-1]){if(h>ans){ans=h;num=s[i-1];}h=1;}else h++;}if(h>ans){//注意不要忽略最后几个都一样的情况 ans=h;num=s[cnt];}int f=0,cnt1=1;for(int i=a;i<=n;i++){for(int j=b;j<=m;j++){unsigned long long v=hash[i][j]+hash[i-a][j-b]*p2[a]*p1[b]-hash[i-a][j]*p2[a]-hash[i][j-b]*p1[b];//再找一遍进行输出 if(v==num&&f==0){for(int k=i-a+1;k<=i;k++){for(int l=j-b+1;l<=j;l++){printf("%c",ch[k][l]);}puts("");}f=1;write(ans),puts("");write(i-a+1),putchar(' '),write(j-b+1);if(ans!=1) puts("");continue;}if(v==num&&f==1){write(i-a+1),putchar(' '),write(j-b+1);cnt++;if(cnt!=ans) puts("");}}}return 0;
}
/*
1 4
1212
1 2
*/

转载于:.html