poj 2185

http://poj.org/problem?id=2185

题意：求最小的模式块，使其无限扩展后包含给你的矩阵块（看别人题解才懂的题意）；

分析：假设存在一个模式块可以满足上述条件，那么必然存在一个起点在（0,0）的模式块满足上述条件；

　　对于每一行，我们找出所有可以满足条件的前缀记录下长度，那么满足所有行的最短的长度就是该模式块的宽r；

　　对于模式块的长，我们把宽r的字符串压缩看出一个字符，然后再进行KMP，找出该字符串的最小循环串，即长l；

答案就是r * l;

 #include<cstdio>

 #include<cstring>

 #include<iostream>

 #include<vector>

 #include<cmath>

 #include<algorithm>

 #include<cmath>

 #include<cstdlib>

 using namespace std;

 const int N = +;

 int f[N];

 void getFail(char *s,int f[]) {

     int m = strlen(s);

     f[] = -;

     for (int i = ; i < m; i++) {

         int j = f[i-];

         while (j != - && s[j+] != s[i]) j = f[j];

         if (s[j+] == s[i]) j++;

         f[i] = j;

     }

  //   for (int i = 0; i < m; i++) cout<<f[i]<<" ";cout<<endl;

 }

 int n,m;

 char mz[N][];

 int cnt[N];

 int check(char *s,int x) {

     int j = ;

     for (int i = ; i < m; i++) {

         if (s[i] != s[j]) return ;

         j++;

         if (j > x) j = ;

     }

     return ;

 }

 void solve(int r){

     f[] = -;

     for (int i = ; i < n; i++) {

         int j = f[i-];

         while (j != - && strcmp(mz[j+],mz[i])) j = f[j];

         if (strcmp(mz[j+],mz[i]) == ) j++;

         f[i] = j;

     }

    // for (int i = 0; i < n; i++) cout<<f[i]<<" ";cout<<endl;

     printf("%d\n",(n -  - f[n-]) * (r));

 }

 int main(){

  //   getFail("ababab",f);

     while (~scanf("%d%d",&n,&m)) {

         memset(cnt,,sizeof(cnt));

         for (int i = ; i < n; i++) {

             scanf("%s",mz[i]);

             getFail(mz[i],f);

             int j = m-;

             while (j != -) {

               //  cout<<m - 1 - f[j]<<endl;

                 cnt[m -  - f[j]]++;

                 j = f[j];

             }

         }

         int r = ;

         for (int i = ; i <= m; i++) if (cnt[i] == n) {

             r = i; break;

         }

         for (int i = ; i < n; i++) {

             mz[i][r] = ;

         }

         solve(r);

     }

     return ;

 }