Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- const int MAX = 100 * 1000 + 47;
- const int LEN = 18; // ceil(log(MAX))
- const int ALP = 128; // Alphabet size
- int CL[LEN][MAX];
- int P[LEN][MAX];
- int CNT[MAX];
- int POS[MAX];
- int lastLev; // P[lastLev] - final array
- void build(const string& s)
- {
- int n = SZ(s);
- FOR(i, 0, n)
- {
- CNT[s[i]]++;
- }
- int sum = 0;
- FOR(i, 0, ALP)
- {
- POS[i] = sum;
- sum += CNT[i];
- }
- FOR(i, 0, n)
- {
- P[0][POS[s[i]]++] = i;
- }
- CL[0][P[0][0]] = 0;
- FOR(i, 1, n)
- {
- int cur = P[0][i];
- int prev = P[0][i - 1];
- CL[0][cur] = CL[0][prev];
- if (s[cur] != s[prev]) CL[0][cur]++;
- }
- lastLev = LEN - 1;
- FOR(it, 1, LEN)
- {
- if ((1 << (it - 1)) >= n)
- {
- lastLev = it - 1;
- break;
- }
- FILL(CNT, 0);
- FOR(i, 0, n)
- {
- CNT[CL[it - 1][i]]++;
- }
- int sum = 0;
- FOR(i, 0, n)
- {
- POS[i] = sum;
- sum += CNT[i];
- }
- FOR(i, 0, n)
- {
- int x = P[it - 1][i] - (1 << (it - 1));
- if (x < 0) x += n;
- int cl = CL[it - 1][x];
- P[it][POS[cl]++] = x;
- }
- CL[it][P[it][0]] = 0;
- FOR(i, 1, n)
- {
- int cur = P[it][i];
- int prev = P[it][i - 1];
- CL[it][cur] = CL[it][prev];
- if (CL[it - 1][cur] != CL[it - 1][prev])
- {
- CL[it][cur]++;
- continue;
- }
- int cc = cur;
- cur += 1 << (it - 1);
- if (cur >= n) cur -= n;
- prev += 1 << (it - 1);
- if (prev >= n) prev -= n;
- if (CL[it - 1][cur] != CL[it - 1][prev])
- {
- CL[it][cc]++;
- }
- }
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement