Time Limit: 3000MS | Memory Limit: 65536K | |
Total Submissions: 10084 | Accepted: 4371 |
Description
Help FJ find the rectangular unit of smallest area that can be repetitively tiled to make up the entire milking grid. Note that the dimensions of the small rectangular unit do not necessarily need to divide evenly the dimensions of the entire milking grid, as indicated in the sample input below.
Input
* Lines 2..R+1: The grid that the cows form, with an uppercase letter denoting each cow's breed. Each of the R input lines has C characters with no space or other intervening character.
Output
Sample Input
2 5
ABABA
ABABA
Sample Output
2
Hint
Source
题意:
找一个最小循环子矩阵。最后一个循环节可以是不完整的。
思路:
【看题的时候完全没思路】
首先我们可以找到一行的所有循环节,一行的最小循环节不一定是最小循环矩阵的行数,因为也许之后有的行时不以这个循环的。S[1~i]的最小循环节就是S[1~i-nxt[i]], S[1~i - nxt[nxt[i]]]是次小循环节,以此类推。我们统计一下每一行循环节的长度,当某个长度k出现的次数为r时,说明每一行都以[1~k]为循环,并且要找到最小的k。
接着我们求列数。将一行的[1~k]作为整体,使用strcmp进行KMP匹配。可以找到列的最小循环节,即列数。
相乘就是答案。
#include <iostream>
#include <set>
#include <cmath>
#include <stdio.h>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
using namespace std;
typedef long long LL;
#define inf 0x7f7f7f7f int r, c;
const int maxn = 1e5 + ;
char s[maxn][];
int nxtrow[maxn][], cntrow[maxn], nxtcol[maxn]; int main()
{
while(scanf("%d%d", &r, &c) != EOF){
memset(cntrow, , sizeof(cntrow));
for(int i = ; i <= r; i++){
scanf("%s", s[i] + );
nxtrow[i][] = ;
for(int j = , k = ; j <= c; j++){
while(k > && s[i][j] != s[i][k + ])k = nxtrow[i][k];
if(s[i][j] == s[i][k + ])k++;
nxtrow[i][j] = k;
//cout<<j<<" "<<nxtrow[i][j]<<endl;
}
for(int j = c; j > ; j = nxtrow[i][j]){
cntrow[c - nxtrow[i][j]]++;
}
}
int row;
for(int i = ; i <= c; i++){
if(cntrow[i] == r){
row = i;
break;
}
}
//cout<<row<<endl;
for(int i = ; i <= r; i++){
s[i][row + ] = ;
} //nxtcol[1] = 0;
for(int i = , j = ; i <= r; i++){
while(j > && strcmp(s[i] + , s[j + ] + ) != )j = nxtcol[j];
if(strcmp(s[i] + , s[j + ] + ) == )j++;
nxtcol[i] = j;
//cout<<i<<" "<<nxtcol[i]<<endl;
} //cout<<nxtcol[r]<<endl;
printf("%d\n", (r - nxtcol[r]) * row);
}
return ;
}