首页 > 代码库 > POJ3690 Constellations 【KMP】
POJ3690 Constellations 【KMP】
| Time Limit: 3000MS | Memory Limit: 65536K | |
| Total Submissions: 5044 | Accepted: 983 |
Description
The starry sky in the summer night is one of the most beautiful things on this planet. People imagine that some groups of stars in the sky form so-called constellations. Formally a constellation is a group of stars that are connected together to form a figure or picture. Some well-known constellations contain striking and familiar patterns of bright stars. Examples are Orion (containing a figure of a hunter), Leo (containing bright stars outlining the form of a lion), Scorpius (a scorpion), and Crux (a cross).
In this problem, you are to find occurrences of given constellations in a starry sky. For the sake of simplicity, the starry sky is given as a N × M matrix, each cell of which is a ‘*‘ or ‘0‘ indicating a star in the corresponding position or no star, respectively. Several constellations are given as a group of T P × Q matrices. You are to report how many constellations appear in the starry sky.
Note that a constellation appears in the sky if and only the corresponding P × Q matrix exactly matches some P × Q sub-matrix in the N × M matrix.
Input
The input consists of multiple test cases. Each test case starts with a line containing five integers N, M, T, P and Q(1 ≤ N, M ≤ 1000, 1 ≤ T ≤ 100, 1 ≤ P, Q ≤ 50).
The following N lines describe the N × M matrix, each of which contains M characters ‘*‘ or ‘0‘.
The last part of the test case describe T constellations, each of which takes P lines in the same format as the matrix describing the sky. There is a blank line preceding each constellation.
The last test case is followed by a line containing five zeros.
Output
For each test case, print a line containing the test case number( beginning with 1) followed by the number of constellations appearing in the sky.
Sample Input
3 3 2 2 2 *00 0** *00 ** 00 *0 ** 3 3 2 2 2 *00 0** *00 ** 00 *0 0* 0 0 0 0 0
Sample Output
Case 1: 1 Case 2: 2
题意：给定一个n行m列的01矩阵，再给定t个p行q列的小01矩阵，求这t个小矩阵有多少个在大矩阵中。
题解：这题我用的是KMP，先把矩阵二进制压缩成整型数组，再求整型数组的next数组，再去跟压缩后的大矩阵匹配。遗憾的是TLE了。。这题先就这样放着，等以后学了AC自动机再试试。
#include <stdio.h>
#define maxn 1002
#define maxm 52
char bigMap[maxn][maxn], smallMap[maxm][maxm];
__int64 smallToInt[maxm], hash[maxn][maxn];
int m, n, t, p, q, next[maxm];
void toInt64(int i, int j)
{
__int64 sum = 0;
for(int k = 0; k < p; ++k)
if(bigMap[i + k][j] == '*') sum = sum << 1 | 1;
else sum <<= 1;
hash[i][j] = sum;
}
void charToHash()
{
int i, j, temp = n - p;
for(i = 0; i <= temp; ++i){
for(j = 0; j < m; ++j) toInt64(i, j);
}
}
void getNext()
{
__int64 sum;
int i, j;
for(i = 0; i < q; ++i){
for(sum = j = 0; j < p; ++j)
if(smallMap[j][i] == '*') sum = sum << 1 | 1;
else sum <<= 1;
smallToInt[i] = sum;
}
i = 0; j = -1;
next[0] = -1;
while(i < q){
if(j == -1 || smallToInt[i] == smallToInt[j]){
++i; ++j;
if(smallToInt[i] == smallToInt[j]) next[i] = next[j];
else next[i] = j; //mode 2
}else j = next[j];
}
}
bool KMP()
{
getNext();
int i, j, k, temp = n - p;
for(k = 0; k <= temp; ++k){
i = j = 0;
while(i < m && j < q){
if(j == -1 || hash[k][i] == smallToInt[j]){
++i; ++j;
}else j = next[j];
}
if(j == q) return true;
}
return false;
}
int main()
{
// freopen("stdin.txt", "r", stdin);
int i, j, ans, cas = 1;
while(scanf("%d%d%d%d%d", &n, &m, &t, &p, &q) != EOF){
if(m + n + t + p + q == 0) break;
for(i = 0; i < n; ++i)
scanf("%s", bigMap[i]);
charToHash(); ans = 0;
while(t--){
for(i = 0; i < p; ++i)
scanf("%s", smallMap[i]);
if(KMP()) ++ans;
}
printf("Case %d: %d\n", cas++, ans);
}
return 0;
}
POJ3690 Constellations 【KMP】