[KMP]poj 2185：Milking Grid

大致题意：
    求一个字符矩阵的最小覆盖子矩阵，输出这个子矩阵的面积。

 

大致题意：
    关于一个字符串的最小覆盖子串可以看这里http://blog.csdn.net/fjsd155/article/details/6866991

    接下来就是把子串扩展到二维，对行和列分别求出最小覆盖子串长度，相乘输出即可

 

#include<iostream>
#include<cstring>
#include<stack>
#include<cstdio>
using namespace std;
const int nMax=100005;
char pat[nMax][80];
int lenc,lenr,next[nMax];

int get_nextR(int c){
    int i,j=-1;
    next[0]=-1;
    for(i=1;i<=lenr;i++){
        while(j>-1&&pat[j+1][c]!=pat[i][c])j=next[j];
        if(pat[j+1][c]==pat[i][c])j++;
        next[i]=j;
    }
  //  cout<<"next 2-"<<lenr-1-next[lenr-1]<<endl;
    return lenr-1-next[lenr-1];
}

int get_nextC(int r){
    int i,j=-1;
    next[0]=-1;
    for(i=1;i<=lenc;i++){
        while(j>-1&&pat[r][j+1]!=pat[r][i])j=next[j];
        if(pat[r][j+1]==pat[r][i])j++;
        next[i]=j;
    }
  //  cout<<"next c-"<<lenc-1-next[lenc-1]<<endl;
    return lenc-1-next[lenc-1];
}

int getnum(int a,int b){     //求最小公倍数
   // cout<<a<<" "<<b<<" ";
    int c,d,e;
    d=a;e=b;
    do{c=a%b;a=b;b=c;}while(c!=0);
  //  cout<<d*e/a<<endl;
    return d*e/a;
}

int main(){
    int r,c,i,j,ans1,ans2;
    while(scanf("%d%d",&lenr,&lenc)!=EOF){
        ans1=1;
        ans2=1;
        for(i=0;i<lenr;i++){
            scanf("%s",pat[i]);
        }
        for(i=0;i<lenr;i++){
            memset(next,0,sizeof(next));
            ans1=getnum(ans1,get_nextC(i));
            if(ans1>=lenc){
                ans1=lenc;
                break;
            }
        }
        for(i=0;i<lenc;i++){
            memset(next,0,sizeof(next));
            ans2=getnum(ans2,get_nextR(i));
            if(ans2>=lenr){
                ans2=lenr;
                break;
            }
        }
        cout<<ans1*ans2<<endl;
    }
    return 0;
}

 

评论

3 楼 proverbs 2013-02-05  

目测你没有看到poj这个题的讨论。。。
这种方法是错误的。。。

2 楼 暴风雪 2012-04-03  

笔良文昌 写道

还是不怎么明白什么是 最小覆盖子串。

解释明白了？

1 楼 笔良文昌 2012-04-03  

还是不怎么明白什么是 最小覆盖子串。