Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /* (c) Vladimir Yakovlev */
- #include <cstdio>
- #include <algorithm>
- using namespace std;
- typedef unsigned int uint;
- #define Max(x,y) ((x)<(y)?(y):(x))
- #define Min(x,y) ((x)<(y)?(x):(y))
- const int MAX = 512;
- const uint P = 1021;
- const uint Q = 4999;
- const uint MAXH = 1048575U;
- int n, m;
- char s[MAX][MAX];
- uint hash[MAX][MAX];
- uint hashTemp[MAX];
- short hashX[MAXH];
- short hashY[MAXH];
- int x1, y1, x2, y2;
- void CountHash(int k)
- {
- int i, j;
- uint pk = 1;
- uint qk = 1;
- for (i=0; i<k; i++)
- {
- pk = pk*P;
- qk = qk*Q;
- }
- for (i=0; i<n; i++)
- {
- int c = 0;
- for (j=0; j<m; j++)
- {
- c = c*P + s[i][j];
- if (j-k >= 0)
- c -= s[i][j-k]*pk;
- if (j-k+1 >= 0)
- hash[i][j-k+1] = c;
- }
- }
- for (j=0; j+k<=m; j++)
- {
- int c = 0;
- for (i=0; i<n; i++)
- {
- c = c*Q + hash[i][j];
- if (i-k >= 0)
- c -= hash[i-k][j]*qk;
- if (i-k+1 >= 0)
- hashTemp[i-k+1] = c;
- }
- for (i=0; i<=n-k; i++)
- hash[i][j] = hashTemp[i];
- }
- }
- bool Check(int i1, int j1, int i2, int j2, int k)
- {
- if (hash[i1][j1] != hash[i2][j2])
- return false;
- for (int i=0; i<k; i++)
- for (int j=0; j<k; j++)
- if (s[i1+i][j1+j] != s[i2+i][j2+j])
- return false;
- x1 = i1;
- y1 = j1;
- x2 = i2;
- y2 = j2;
- return true;
- }
- bool Find(int k)
- {
- CountHash(k);
- memset(hashX, -1, sizeof(hashX));
- for (int i=0; i<=n-k; i++)
- for (int j=0; j<=m-k; j++)
- {
- uint u;
- for (u = hash[i][j]%MAXH; hashX[u] != -1; u = (u+1)%MAXH)
- if (Check(hashX[u], hashY[u], i, j, k))
- return true;
- hashX[u] = i;
- hashY[u] = j;
- }
- return false;
- }
- int main()
- {
- #ifndef ONLINE_JUDGE
- freopen("input.txt", "rt", stdin);
- freopen("output.txt", "wt", stdout);
- #endif
- scanf("%d%d", &n, &m);
- for (int i=0; i<n; i++)
- scanf("%s", s[i]);
- int l = 0;
- int r = Min(n, m);
- while (l < r)
- {
- int c = (l+r+1) / 2;
- if (Find(c))
- l = c;
- else
- r = c-1;
- }
- if (l == 0)
- {
- printf("0\n");
- }
- else
- {
- Find(l);
- printf("%d\n%d %d\n%d %d\n", l, x1+1, y1+1, x2+1, y2+1);
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement