Andrew Stankevich’s Contest #11解题报告 » ZOJ3367

ZOJ3367.cpp

```#include <cstdio>
#include <cstring>

struct anonymous {
int x, y, l, r, t, b, s;
} tmp, ans;

char a[150][150], b[50][50];
int c[50], l[50], r[50];

int main() {
bool flag;
int m1, n1, m2, n2;

while (scanf("%d%d", &m1, &n1) != EOF) {
memset(a, '#', sizeof(a));
for (int i = 0; i < m1; ++i) {
scanf("%s", a[50 + i] + 50);
}
scanf("%d%d", &m2, &n2);
for (int i = 0; i < m2; ++i) {
scanf("%s", b[i]);
}

flag = false;
ans.s = 0;
for (tmp.x = -m2 + 1; tmp.x < m1; ++tmp.x) {
for (tmp.y = -n2 + 1; tmp.y < n1; ++tmp.y) {
memset(c, 0, sizeof(c));
for (int i = 0; i < m2; ++i) {
for (int j = 0; j < n2; ++j) {
if (a[50 + i + tmp.x][50 + j + tmp.y] != b[i][j]) {
c[j] = 0;
} else {
++c[j];
}
}

for (int j = 0; j < n2; ++j) {
int k = j - 1;
while (k >= 0 && c[k] >= c[j]) {
k = l[k];
}
l[j] = k;
}

for (int j = n2 - 1; j >= 0; --j) {
int k = j + 1;
while (k < n2 && c[k] >= c[j]) {
k = r[k];
}
r[j] = k;
}

for (int j = 0; j < n2; ++j) {
tmp.l = l[j] + 1;
tmp.r = r[j];
tmp.t = i - c[j] + 1;
tmp.b = i + 1;
tmp.s = (tmp.r - tmp.l) * (tmp.b - tmp.t);
if (tmp.s > ans.s) {
ans = tmp;
} else if (tmp.s == ans.s) {
flag = true;
}
}
}
}
}

if (ans.s == 0) {
puts("0 0");
} else {
printf("%d %d\n%d %d\n%d %d\n",
ans.b - ans.t,
ans.r - ans.l,
ans.x + ans.t + 1,
ans.y + ans.l + 1,
ans.t + 1,
ans.l + 1);
if (flag) {
}
}
}

return 0;
}

//real	0m2.844s
//user	0m2.836s
//sys	0m0.008s

//Run ID  	Submit Time  	Judge Status  	Problem ID  	Language  	Run Time(ms)  	Run Memory(KB)  	User Name  	Admin
//176 	2010-07-08 14:39:48 	Accepted 	asc11f 	C++ 	4330 	200 	watashi@Zodiac 	Source
```