Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- 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;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement