POJ 2185 Milking Grid [KMP]

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
typedef long long ll;
const int N=1e4+5,M=80;
int n,m,k,fail[N];
char s[N][M];
bool cmp1(int a,int b){
    for(int i=1;i<=m;i++) if(s[a][i]!=s[b][i]) return false;
    return true;
}
bool cmp2(int a,int b){
    for(int i=1;i<=k;i++) if(s[i][a]!=s[i][b]) return false;
    return true;
}
void getFail(int n,bool (*cmp)(int a,int b)){
    fail[1]=0;
    for(int i=2;i<=n;i++){
        int j=fail[i-1];
        while(j&&!cmp(j+1,i)) j=fail[j];
        fail[i]=cmp(j+1,i)?j+1:0;
    }
}

int main(){
//    freopen("in.txt","r",stdin);
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%s",s[i]+1);
    getFail(n,cmp1);
    k=n-fail[n];
    memset(fail,0,sizeof(fail));
    getFail(m,cmp2);
    printf("%d",k*(m-fail[m]));
}