POJ 2185 KMP (最小循环模块)

/*题意：求最小循环模块的面积
必然存在一个最小循环模块的起点为(0,0)，
对于每一行，对每一个循环串的长度做记录，满足所有行条件的最短长度即为宽b
对于长度，颗粒利用strcmp把每一行的字符串看成一个字符，然后进行KMP就可以得到长度
*/

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
char s[10005][105];
int cnt[10005],next[10005],h,w;
void getnext(int c)
{
    int i=0,j=-1;
    next[0]=-1;
    while(i<w)
    {
        if(j==-1||s[c][i]==s[c][j])
        {
            i++;
            j++;
            next[i]=j;
        }
        else
            j=next[j];
    }
}
void kmp(int b)
{
    int i=0,j=-1;
    next[0]=-1;
    while(i<h)
    {
        if(j==-1||(strcmp(s[i],s[j])==0))
        {
            i++;
            j++;
            next[i]=j;
        }
        else
            j=next[j];
    }
    printf("%d\n",(h-next[h])*b);
}

int main()
{
    int i,j,b;
    while(scanf("%d%d",&h,&w)!=EOF)
    {
        memset(cnt,0,sizeof(cnt));
        for(i=0; i<h; i++)
        {
            scanf("%s",s[i]);
            getnext(i);
            j=w;
            while(j)
            {
                cnt[w-next[j]]++;
                j=next[j];
            }
        }
        for(i=1; i<=w; i++)
        {
            if(cnt[i]==h)
            {
                b=i;
                break;
            }
        }
        for(i=0; i<h; i++)
            s[i][b]=0;
        kmp(b);
    }
    return 0;
}
/*
2 5
ABABA
ABABA
2
2 8
ABCDEFAB
ABCDEABC
16
2 8
ABCDEFAB
AAAABAAA
12
3 5
ABABA
ABABA
ABABA
2
*/

POJ 2185 KMP (最小循环模块),布布扣,bubuko.com

POJ 2185 KMP (最小循环模块)

原文：http://blog.csdn.net/littlefool5201314/article/details/23102463