Match
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 918 Accepted Submission(s): 298
Problem Description
There is a matrix of size n*n whose elements are either 0 or 1. Now your task is to find out that given a matrix of size m*m whose elements are also 0 or 1 whether it is a sub-matrix of the previous matrix.
Input
There is a matrix of size n*n whose elements are either 0 or 1. Now your task is to find out that given a matrix of size m*m whose elements are also 0 or 1 whether it is a sub-matrix of the previous matrix.
Output
If the second matrix is a sub-matrix of the first one, print “Yes” on a single line. Otherwise print “No”.
Sample Input
4 2
0 0 0 1
0 1 0 1
1 0 1 0
0 0 0 0
1 0
0 0
3 2
0 0 1
0 1 0
1 0 0
0 0
1 1
Sample Output
好題，昨天剛學了rabin_karp ，還是字符串匹配算法 （求t在p中的位置 ，令m=strlen(t)）
其實就是hash嘛，
根據horner法則【霍納法則】來hash
horner法則百度去
我們hash出了t的值
然后我們要求出p中所有連續的長度為m的串的hash值
這個過程我們可以用horner法則推出一個關系式，相鄰的兩個長度為m的串的hash值之間的關系
這個自己推一下就好了，
所以我們求下一個hash值時候可以通過關系式直接求出，常數時間，
知道我們求出一個hash值與t的hash值相等，或者找不到
效率不解釋了
這個題硬搞可以卡時過
然后我們可以用rk搞
上面講的是rk是一維的，這個顯然是二維的
怎么辦呢，我們可以壓縮成一維的啊
不解釋，這個跟動歸中的最小子矩陣和，等有異曲同工之妙
上個垃圾的rk代碼
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cassert>
#include <iostream>
#include <sstream>
#include <fstream>
#include <map>
#include <set>
#include <vector>
#include <queue>
#include <algorithm>
#include <iomanip>
using namespace std;
int getv(char x)
{
return (x-'0');
}
int rk(char t[],char p[],int d)
{
int n=strlen(t);
int m=strlen(p);
long long h=(long long )pow(double(d),m-1);
int pp=0;
int tt=0;
for(int i=0;i<m;i++)
{
pp=d*pp+getv(p[i]);
tt=d*tt+getv(t[i]);
}
for(int s=0;s<=n-m;s++)
{
cout<<"pp,tt is"<<pp<<","<<tt<<endl;
if(pp==tt)
return s;
if (s<n-m)
{
tt=getv(t[s+m])+d*(tt-h*getv(t[s]));
}
}
return -1;
}
int main()
{
char set1[15]={"0123456789"};//串由0 - 9 組成
char set2[30]={"abcdefghijklmnopqrstuvwxyz"};
char p[10]={"2365"};
char t[]={"258569236589780"};
int d=10;
int i=rk(t,p,d);
printf("pos %d\n",i);
return 0;
}
code
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cassert>
#include <iostream>
#include <sstream>
#include <fstream>
#include <map>
#include <set>
#include <vector>
#include <queue>
#include <algorithm>
#include <iomanip>
#define maxn 1005
#define mod 10003
#define r 2
using namespace std;
int n,m;
int a[maxn][maxn],b[maxn][maxn];
int pb[maxn];
int tmp[maxn];
int tv;
void ready()
{
pb[0]=1;
for(int i=1; i<=1000; i++) pb[i]=2*pb[i-1] % mod;
}
int main()
{
int i,j,p,q,ans;
ready();
while(scanf("%d%d",&n,&m)!=EOF)
{
for(i=1; i<=n; i++)
for(j=1; j<=n; j++)
scanf("%d",&a[i][j]);
for(i=1; i<=m; i++)
for(j=1; j<=m; j++)
scanf("%d",&b[i][j]);
tv=0;
for(i=1; i<=m; i++)
{
tmp[i]=0;
for(j=1; j<=m; j++)
tmp[i]=(tmp[i]*r+b[j][i])% mod;
tv=(tv*r+tmp[i])%mod;
}
memset(tmp,0,sizeof(tmp));
for(j=1; j<=n; j++)
{
tmp[j]=0;
for(i=1; i<=m; i++)
tmp[j]=(tmp[j]*r+a[i][j])%mod;
}
bool flag;
flag=0;
for(i=m; i<=n&&!flag; i++)
{
ans=0;
for(j=1; j<=n&&!flag; j++)
if(j<m)
{
ans=(ans*r+tmp[j])%mod;
}
else
{
ans=((ans-tmp[j-m]*pb[m-1])*r+tmp[j])%mod;
if((ans+mod)%mod==tv)
{
if(a[i][j]==b[m][m]&&a[i][j-m+1]==b[m][1]&&a[i-m+1][j]==b[1][m]&&a[i-m+1][j-m+1]==b[1][1])
flag=1;
else flag=0;
for( p=1; p<=m&&flag; p++)
for(q=1; q<=m&&flag; q++)
{
if(b[p][q]!=a[i-m+p][j-m+q])
{
flag=0;
break;
}
if(flag==0) break;
}
}
}
if(i<n)
{
for(j=1; j<=n; j++)
tmp[j]=((tmp[j]-a[i-m+1][j]*pb[m-1])*r+a[i+1][j])%mod;
}
}
if(flag)
printf("Yes\n");
else printf("No\n");
}
return 0;
}