1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 |
uLL ha1[maxn], pw1[maxn], ha2[maxn], pw2[maxn]; int len; char str[maxn]; void Init(){ pw1[0] = pw2[0] = 1; for(int i = 1; i < maxn; i++){ pw1[i] = pw1[i - 1] * 123; pw2[i] = pw2[i - 1] * 29; } } void build(){ for(int i = 1; i <= len; i++){ ha1[i] = ha1[i - 1] * 123 + str[i]; ha2[i] = ha2[i - 1] * 29 + str[i]; } } uLL getHash1(int x, int L){ return ha1[x + L - 1] - ha1[x - 1] * pw1[L]; } uLL getHash2(int x, int L){ return ha2[x + L - 1] - ha2[x - 1] * pw2[L]; } int lcp(int x, int y){ int l = 0, r = len - max(x, y) + 1; while(l <= r){ int mid = (l + r) >> 1; if(getHash1(x, mid) == getHash1(y, mid) && getHash2(x, mid) == getHash2(y, mid)) l = mid + 1; else r = mid - 1; } return r; } |