posts - 64, comments - 4, trackbacks - 0, articles - 0

hdu_3531 Match

Posted on 2010-08-16 19:21 acronix 阅读(495) 评论(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]*+ b[i][j]) % mod;
              den 
= (den*+ 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]*+ 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*+ 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])*+ a[i+1][j])%mod;
         }   
         
if (flag == true)
            printf(
"Yes\n");
         
else printf("No\n");   
          
    }
    
return 0;



比较行列1的个数的算法:

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理