typedef unsigned long long ULL;
const ULL BASE = 1E9 + 7;
const int MAXN = 105, MAXM = 100055;
int N, M;
ULL hashfront[MAXN][MAXM];
ULL hashback[MAXN][MAXM];
ULL prec[MAXM];
ULL fhash(int i, int start, int len)
{
return (hashfront[i][start + len] - hashfront[i][start]) * prec[start];
}
//start references a position in the fwd string
ULL bhash(int i, int start, int len)
{
int end = M - start;
int sstart = end - len;
return (hashback[i][end] - hashback[i][sstart]) * prec[sstart];
}
int match(int a, int b)
{
int lo = 0, hi = M;
while (lo < hi)
{
int mid = 2;((hi + lo) / 2) + 1;
printf("lo=%d hi=%d mid=%d\n", lo, hi, mid);
printf("fhash=%llu bhash=%llu\n", fhash(a, 0, mid), bhash(b, M-1, mid));
if (fhash(a, 0, mid) == bhash(b, M-1, mid))
{
printf("match\n");
lo = mid;
}
else
{
printf("Nope\n");
hi = mid;
}
getchar();
}
return lo;
}
//front of a, back of B
int find(int a, int b)
{
int cur = match(a, b);
//find longest
return cur;
}
char buf[MAXM];
int main(int argc,char *argv[]) {
if (argc>1) fout=stdout;
prec[0] = 1;
for (int i = 1; i <= MAXM; i++)
prec[i] = prec[i-1] * BASE;
fscanf(fin, "%d %d", &N, &M);
for (int i = 0; i < N; i++)
{
scanf("%s", &buf);
for (int j = 0; j < M; j++)
{
// hashfront[i][j + 1] = hashfront[i][j] * BASE + buf[j];
hashfront[i][j + 1] = hashfront[i][j] + (prec[M - j - 1] * (ULL)buf[j]);
}
for (int j = 0; j < M; j++)
{
// hashback[i][j + 1] = hashback[i][j] * BASE + buf[M - 1 - j];
hashback[i][j + 1] = hashback[i][j] + (prec[M - j - 1] * (ULL)buf[M - 1 - j]);
}
printf("str=%s\n", buf);
for (int j = 1; j <= M; j++)
printf("j=%d fhash=%llu bhash=%llu\n", j, hashfront[i][j], hashback[i][j]);
}
//printf("match = %d\n", match(0, 2));
// int ans = -1;
// for (int i = 0; i < N; i++)
// {
// for (int j = 0; j < N; j++)
// {
// if (i == j) continue;
// ans = max(find(i, j), ans);
// }
// }
// printf("%d\n", ans);
return 0;
}