poj 2185 Milking Grid

求最小重復矩陣。

        首先得證明一個結論，最小重復矩陣一定是靠著左上角的。這個可以利用黏貼技術證明。如果有一個不靠左上角的重復矩陣，必然可以通過黏貼得到一個大小相同的靠左上角的矩陣，這個自己畫畫就明白了。

        第二個就是s=len-next[len]等於一個字符串的最小循環節。至於它是循環節利用畫圖可以看出來。

        至於是最小的可以這麼考慮，如果存在更小的循環節，必然能得到更大的next值，與next數組矛盾。

        還有一點不是s的整數倍的必然不是循環節。

        但是此題麻煩的地方在於，可以黏貼在空白的地方。這個需要對多出來的部分再次求循環節。

[cpp]
#include <iostream>  
#include <cstdio>  
#include <cstring>  
using namespace std; 
const int maxn=1e4+9,maxm=80; 
char a[maxn][maxm],b[maxm][maxn]; 
int count[maxn],next[maxn]; 
int n,m; 
 
void kmp(char a[],int n) 
{ 
    next[0]=0; 
    next[1]=0; 
    for(int i=2;i<=n;i++) 
    { 
        int t=i-1; 
        while(t&&a[i]!=a[next[t]+1]) 
        t=next[t]; 
        next[i]=next[t]+(a[i]==a[next[t]+1]); 
    } 
} 
 
void work(char a[],int n) 
{ 
 
    kmp(a,n); 
    int t=n-next[n]; 
    int ret=0,len=n; 
    while(ret+t!=n) 
    { 
        for(int i=t;i+ret<=n;i+=t) 
        count[i+ret]++; 
        ret+=len/t*t; 
        len=len-len/t*t; 
        t=len-next[len]; 
    } 
    count[n]++; 
} 
 
void solve() 
{ 
    int c,r; 
    memset(count,0,sizeof(count)); 
    for(int i=1;i<=n;i++) 
    work(a[i],m); 
    for(int i=1;i<=m;i++) 
    if(count[i]>=n) 
    { 
        c=i; 
        break; 
    } 
    memset(count,0,sizeof(count)); 
    for(int i=1;i<=m;i++) 
    work(b[i],n); 
    for(int i=1;i<=n;i++) 
    if(count[i]>=m) 
    { 
        r=i; 
        break; 
    } 
 
    printf("%d\n",c*r); 
} 
int main() 
{ 
//    freopen("in.txt","r",stdin);  
    while(scanf("%d %d",&n,&m)!=EOF) 
    { 
        for(int i=1;i<=n;i++) 
        scanf("%s",a[i]+1); 
 
        for(int i=1;i<=n;i++) 
        for(int j=1;j<=m;j++) 
        b[j][i]=a[i][j]; 
 
        solve(); 
    } 
    return 0; 
} 

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn=1e4+9,maxm=80;
char a[maxn][maxm],b[maxm][maxn];
int count[maxn],next[maxn];
int n,m;

void kmp(char a[],int n)
{
    next[0]=0;
    next[1]=0;
    for(int i=2;i<=n;i++)
    {
        int t=i-1;
        while(t&&a[i]!=a[next[t]+1])
        t=next[t];
        next[i]=next[t]+(a[i]==a[next[t]+1]);
    }
}

void work(char a[],int n)
{

    kmp(a,n);
    int t=n-next[n];
    int ret=0,len=n;
    while(ret+t!=n)
    {
        for(int i=t;i+ret<=n;i+=t)
        count[i+ret]++;
        ret+=len/t*t;
        len=len-len/t*t;
        t=len-next[len];
    }
    count[n]++;
}

void solve()
{
    int c,r;
    memset(count,0,sizeof(count));
    for(int i=1;i<=n;i++)
    work(a[i],m);
    for(int i=1;i<=m;i++)
    if(count[i]>=n)
    {
        c=i;
        break;
    }
    memset(count,0,sizeof(count));
    for(int i=1;i<=m;i++)
    work(b[i],n);
    for(int i=1;i<=n;i++)
    if(count[i]>=m)
    {
        r=i;
        break;
    }

    printf("%d\n",c*r);
}
int main()
{
//    freopen("in.txt","r",stdin);
    while(scanf("%d %d",&n,&m)!=EOF)
    {
        for(int i=1;i<=n;i++)
        scanf("%s",a[i]+1);

        for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        b[j][i]=a[i][j];

        solve();
    }
    return 0;
}