Posted on 2010-08-16 19:21
acronix 阅读(510)
评论(0) 编辑 收藏 引用 所属分类:
hzshuai解题报告
题意：给你两个0-1矩阵，编程验证后一个矩阵是不是前一个矩阵的一部分。
分析：
解法一：在N*N中枚举M*M大小矩阵的左上角，然后比较这部分的矩阵行列的1个数是否相等，若全相等则一一比较。用C++交，压着时间过。
解法二：字符串匹配的Rabin_Karp算法的二维拓展。
下面是摘要RK算法的描述：
1. 问题描述
给定目标字符串 T[0..n-1] （基于 0 的数组，数组长度为 n ），和模式串 P[0..m-1] ，问 P 可否匹配 T 中的任意子串，如果可以，返回匹配位置。
2. 问题分析
直观分析
brute-force 的蛮力法，适用于较小规模的字符串匹配。
优化
主要介绍 3 种优化办法，分别具体为： Rabin-Karp 算法，有限自动机和 KMP 算法。本小节主要介绍 Rabin-Karp 算法。
得出算法
Rabin-Karp 算法（以下简称为 RK 算法），是基于这样的思路：即把串看作是字符集长度进制的数，由数的比较得出字符串的比较结果。例如，给定字符集为∑ ={0,1,2,3,4,5,6,7,8,9} ，∑长度为 d=10 ，那么任何以∑为字符集的串都可看作 d （此处为 10 ）进制的数。
记模式串 P[0..n-1] 对应的数值为 P ， T[0..n-1] 所有长度为 m 的子串对应的数值为 ts ，设 P 和 T 都是基于字符集长度为 | ∑ |=d 的字符串。
那么， ts 即为 T[s..s+m] 对应的数值，这里 0<=s<=n-m-1 。
P = P[m]+d*(P[m-1]+d*(P[m-2]+..)))
同样 t0 也可类似求得。
最重要的是如何从 ts 求出 ts+1 。
ts+1 =T[s+m]+d*(ts +dm-1 *T[s])
注：此处是该算法的关键，即在常数时间内能够计算出下一个 m 长度的字串对应的数值。初看比较抽象，举个例子就比较明白了，设 x=12345 ，现在是已知长度为 3 的数值 234 ，现在要求 345 对应的数值，可以这样来得到： 345 = 5 + 10*(234-102 *2)
3. 算法描述
求出所有 m 长度子串所对应的数值，对数值进行比较，继而得出子串是否匹配。当模式串长度很大时，这时对应的数值会很大，比较起来比较麻烦，可使用对一个大奇数（9997）取模后进行比较。
4. 具体实现
这里实现的只是m值较小时的情形，大整数需要特定的类的支持（如可自定义大整数类），选取10进制的数是为了方便起见，当然字母也是OK的。
回到本题，因为是0-1矩阵，所以d=2，我们可以对于每一个M*M的子矩阵以列连接成一维的数组，并求出此子矩阵的RK值，然后与给出的M*M的矩阵的RK比较，若相等，则一一比较。
Rabin_Karp算法的代码：
#include <cstdio>
#include <time.h>
const int r = 2;
const int mod = 9997;
bool a[1010][1010],b[510][510];
int pr[1010],temp[1010],den,ans;
int n,m;
int main()
{
int i,j,k,q,p;
bool flag;
pr[0] = 1;
for (i = 1; i <= 1001; i ++)
pr[i] = (pr[i-1]*r) % mod;
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]);
if (m > n)
{
printf("No\n");
continue;
}
den = 0; //计算m*m的矩阵的RK值
for (j = 1; j <= m; j++)
{
temp[j] = 0;
for (i = 1; i <= m; i++)
temp[j] = (temp[j]*r + b[i][j]) % mod;
den = (den*r + temp[j]) % mod;
}
//计算n*n的举证前m行的各列RK值
temp[0] = 0;
for (j = 1; j <= n; j++)
{
temp[j] = 0;
for (i = 1; i <= m; i++)
temp[j] = (temp[j]*r + a[i][j]) % mod;
}
flag = false;
for (i = m; i <= n && !flag; i++)
{
ans = 0;
for (j = 1; j <= n && !flag; j++)
{
if (j < m)
ans = (ans*r + temp[j]) % mod; //求子m*m矩阵的RK值
else {
//注意减去第j-m列的RK值
ans = ((ans - temp[j-m]*pr[m-1]) * r + temp[j] ) % mod;
if ((ans + mod) % mod == den)
{
if (a[i][j] == b[m][m] && a[i-m+1][j-m+1] == b[1][1]
&& a[i][j-m+1] == b[m][1] && a[i-m+1][j] == b[1][m])
flag = true;
else flag = false;
for (p = 1; p <= m && flag; p++)
for (q= 1; q <= m && flag; q++)
if (a[i-m+p][j-m+q] != b[p][q])
flag = false;
}
}
}
//求得i+1前m行各列的RK值
if (i < n)
for (j = 1; j <= n; j ++)
temp[j] = ((temp[j] - a[i-m+1][j]*pr[m-1])*r + a[i+1][j])%mod;
}
if (flag == true)
printf("Yes\n");
else printf("No\n");
}
return 0;
}
比较行列1的个数的算法：
#include <cstdio>
#include <time.h>
bool a[1010][1010],b[510][510];
int cnta[1010][1010],cntb[510],t;
int counta[1010][1010],countb[510];
int n,m;
int main()
{
// int now = clock();
int i,j,k,q,p;
bool flag;
while (scanf("%d %d",&n,&m) != EOF)
{
for (i = 1; i <= n; i ++)
{
cnta[i][0] = counta[0][i] = 0;
for (j = 1; j <= n; j ++)
{
scanf("%d",&t);
a[i][j] = (t == 1 ? true : false);
cnta[i][j] = t + cnta[i][j-1];
counta[i][j] = t + counta[i-1][j];
}
}
for (i = 1; i <= m; i++)
countb[i] = 0;
for (i = 1; i <= m; i++)
{
cntb[i] = 0;
for (j = 1; j <= m; j++)
{
scanf("%d",&t);
b[i][j] = (t == 1 ? true : false);
cntb[i] = t + cntb[i];
countb[j] = countb[j] + t;
}
}
if (m > n)
{
printf("No\n");
continue;
}
flag = false;
for (i = 1; i <= n-m+1 && flag == false; i++)
for (j = 1; j <= n-m+1 && flag == false; j++)
{ //printf("i = %d,j = %d\n",i,j);
if (a[i][j] == b[1][1] && a[i+m-1][j+m-1] == b[m][m] &&
a[i][j+m-1] == b[1][m] && a[i+m-1][j] == b[m][1])
{
flag = true;
for (k = i ; k <= i+m-1 && flag ; k ++)
if (cnta[k][j+m-1] - cnta[k][j-1] != cntb[k-i+1])
flag = false;
for (k = j; k <= j+m-1&& flag; k++)
if (counta[i+m-1][k] - counta[i-1][k] != countb[k-j+1])
flag =false;
if (flag)
{
for ( p = 1; p <= m && flag; p++)
for ( q = 1; q <= m && flag; q++)
if (a[p+i-1][q+j-1] != b[p][q])
flag = false;
}
}
}
if (flag == true)
printf("Yes\n");
else printf("No\n");
}
// printf("%dms\n",clock()-now);
return 0;
}