PKU 2185 Milking Grid

KMP.久しぶりにオンラインジャッジをやるにはいい問題だと思います。

これでPKUのUSACO Unsolvedは16→13に。

#include<stdio.h>
#include<algorithm>
using namespace std;
char str[10000][76];
int fail[10001];
int main(){
	int a,b;
	scanf("%d%d",&a,&b);
	for(int i=0;i<a;i++)scanf("%s",str[i]);
	int ret=1;
	
	for(int i=1;i<a;i++){
		int at=fail[i];
		while(1){
			bool ok=true;
			for(int j=0;j<b;j++)if(str[i][j]!=str[at][j])ok=false;
			if(ok){
				fail[i+1]=at+1;
				break;
			}else{
				if(at==0){
					fail[i+1]=0;
					break;
				}
				at=fail[at];
			}
		}
	}
	ret*=a-fail[a];
	for(int i=0;i<10001;i++)fail[i]=0;
	for(int i=1;i<b;i++){
		int at=fail[i];
		while(1){
			bool ok=true;
			for(int j=0;j<a;j++)if(str[j][i]!=str[j][at])ok=false;
			if(ok){
				fail[i+1]=at+1;
				break;
			}else{
				if(at==0){
					fail[i+1]=0;
					break;
				}
				at=fail[at];
			}
		}
	}
	ret*=b-fail[b];
	printf("%d\n",ret);
}