SPOJ/NSUBSTR.cc

   1 #define LOCAL
   2
   3 /** template.h ver 0.5.2 */
   4
   5 #include <cassert>
   6 #include <cctype>
   7 #include <climits>
   8 #include <cmath>
   9 #include <cstdio>
  10 #include <cstdlib>
  11 #include <cstring>
  12 #include <ctime>
  13 #include <deque>
  14 #include <list>
  15 #include <map>
  16 #include <queue>
  17 #include <set>
  18 #include <stack>
  19 #include <vector>
  20 #include <fstream>
  21 #include <iomanip>
  22 #include <iostream>
  23 #include <sstream>
  24 #include <algorithm>
  25 #include <bitset>
  26 #include <complex>
  27 #include <functional>
  28 #include <limits>
  29 #include <numeric>
  30 #include <string>
  31 #include <typeinfo>
  32 #include <utility>
  33 #include <valarray>
  34
  35 #define REP(i, n) for (int i = 0; i < int(n); ++i)
  36 #define FOR(i, a, b) for (int i = int(a); i < int(b); ++i)
  37 #define DWN(i, b, a) for (int i = int(b - 1); i >= int(a); --i)
  38 #define REP_1(i, n) for (int i = 1; i <= int(n); ++i)
  39 #define FOR_1(i, a, b) for (int i = int(a); i <= int(b); ++i)
  40 #define DWN_1(i, b, a) for (int i = int(b); i >= int(a); --i)
  41 #define REP_C(i, n) for (int n____ = int(n), i = 0; i < n____; ++i)
  42 #define FOR_C(i, a, b) for (int b____ = int(b), i = a; i < b____; ++i)
  43 #define DWN_C(i, b, a) for (int a____ = int(a), i = b - 1; i >= a____; --i)
  44 #define REP_N(i, n) for (i = 0; i < int(n); ++i)
  45 #define FOR_N(i, a, b) for (i = int(a); i < int(b); ++i)
  46 #define DWN_N(i, b, a) for (i = int(b - 1); i >= int(a); --i)
  47 #define REP_1_C(i, n) for (int n____ = int(n), i = 1; i <= n____; ++i)
  48 #define FOR_1_C(i, a, b) for (int b____ = int(b), i = a; i <= b____; ++i)
  49 #define DWN_1_C(i, b, a) for (int a____ = int(a), i = b; i >= a____; --i)
  50 #define REP_1_N(i, n) for (i = 1; i <= int(n); ++i)
  51 #define FOR_1_N(i, a, b) for (i = int(a); i <= int(b); ++i)
  52 #define DWN_1_N(i, b, a) for (i = int(b); i >= int(a); --i)
  53 #define REP_C_N(i, n) for (n____ = int(n), i = 0; i < n____; ++i)
  54 #define FOR_C_N(i, a, b) for (b____ = int(b), i = a; i < b____; ++i)
  55 #define DWN_C_N(i, b, a) for (a____ = int(a), i = b - 1; i >= a____; --i)
  56 #define REP_1_C_N(i, n) for (n____ = int(n), i = 1; i <= n____; ++i)
  57 #define FOR_1_C_N(i, a, b) for (b____ = int(b), i = a; i <= b____; ++i)
  58 #define DWN_1_C_N(i, b, a) for (a____ = int(a), i = b; i >= a____; --i)
  59
  60 #define ECH(it, A) for (__typeof(A.begin()) it = A.begin(); it != A.end(); ++it)
  61 #define REP_S(it, str) for (char *it = str; *it; ++it)
  62 #define REP_G(it, u) for (int it = adj[u]; it != -1; it = next[it])
  63 #define DO(n) for (int ____n##__line__ = n; ____n##__line__--;)
  64 #define REP_2(i, j, n, m) REP(i, n) REP(j, m)
  65 #define REP_2_1(i, j, n, m) REP_1(i, n) REP_1(j, m)
  66 #define REP_3(i, j, k, n, m, l) REP(i, n) REP(j, m) REP(k, l)
  67 #define REP_3_1(i, j, k, n, m, l) REP_1(i, n) REP_1(j, m) REP_1(k, l)
  68
  69 #define COPY(a, b) memcpy(a, b, sizeof a)
  70 #define Rush int T____; RD(T____); DO(T____)
  71 #define Display(A, n, m) {                   \
  72   REP(i, n) {                                \
  73     REP(j, m) std::cout << A[i][j] << " ";   \
  74     std::cout << endl;                       \
  75   }                                          \
  76 }
  77
  78 #define Display_1(A, n, m) {                 \
  79   REP_1(i, n) {                              \
  80     REP_1(j, m) std::cout << A[i][j] << " "; \
  81     std::cout << endl;                       \
  82   }                                          \
  83 }
  84 #pragma comment(linker, "/STACK:16777216")
  85
  86 typedef unsigned uint;
  87 typedef long long int64;
  88 typedef unsigned long long uint64;
  89
  90 const int dx[] = {-1, 0, 1, 0};
  91 const int dy[] = {0, 1, 0, -1};
  92
  93 const int MOD = 1000000007;
  94 const int INF = 0x3f3f3f3f;
  95 //const int64 INF = 1LL << 60;
  96 const double eps = 1e-9;
  97 const double oo = 1e20;
  98
  99 #ifdef M_PI
 100 const double PI = M_PI;
 101 #else
 102 const double PI = acos(-1.0);
 103 #endif
 104
 105 template <typename T> inline T& RD(T &);
 106 template <typename T> inline void OT(const T &);
 107 inline int64 RD() { int64 x; return RD(x); }
 108 inline char& RC(char &c) { scanf(" %c", &c); return c; }
 109 inline char RC() { char c; return RC(c); }
 110 //inline char& RC(char &c) { c = getchar(); return c; }
 111 //inline char RC() { return getchar(); }
 112 inline double& RF(double &x) { scanf("%lf", &x); return x; }
 113 inline double RF() { double x; return RF(x); }
 114 inline char* RS(char *s) { scanf("%s", s); return s; }
 115
 116 template <typename T0, typename T1> inline T0& RD(T0 &x0, T1 &x1) { RD(x0), RD(x1); return x0; }
 117 template <typename T0, typename T1, typename T2> inline T0& RD(T0 &x0, T1 &x1, T2 &x2) { RD(x0), RD(x1), RD(x2); return x0; }
 118 template <typename T0, typename T1, typename T2, typename T3> inline T0& RD(T0 &x0, T1 &x1, T2 &x2, T3 &x3) { RD(x0), RD(x1), RD(x2), RD(x3); return x0; }
 119 template <typename T0, typename T1, typename T2, typename T3, typename T4> inline T0& RD(T0 &x0, T1 &x1, T2 &x2, T3 &x3, T4 &x4) { RD(x0), RD(x1), RD(x2), RD(x3), RD(x4); return x0; }
 120 template <typename T0, typename T1, typename T2, typename T3, typename T4, typename T5> inline T0& RD(T0 &x0, T1 &x1, T2 &x2, T3 &x3, T4 &x4, T5 &x5) { RD(x0), RD(x1), RD(x2), RD(x3), RD(x4), RD(x5); return x0; }
 121 template <typename T0, typename T1, typename T2, typename T3, typename T4, typename T5, typename T6> inline T0& RD(T0 &x0, T1 &x1, T2 &x2, T3 &x3, T4 &x4, T5 &x5, T6 &x6) { RD(x0), RD(x1), RD(x2), RD(x3), RD(x4), RD(x5), RD(x6); return x0; }
 122 template <typename T0, typename T1> inline void OT(const T0 &x0, const T1 &x1) { OT(x0), OT(x1); }
 123 template <typename T0, typename T1, typename T2> inline void OT(const T0 &x0, const T1 &x1, const T2 &x2) { OT(x0), OT(x1), OT(x2); }
 124 template <typename T0, typename T1, typename T2, typename T3> inline void OT(const T0 &x0, const T1 &x1, const T2 &x2, const T3 &x3) { OT(x0), OT(x1), OT(x2), OT(x3); }
 125 template <typename T0, typename T1, typename T2, typename T3, typename T4> inline void OT(const T0 &x0, const T1 &x1, const T2 &x2, const T3 &x3, const T4 &x4) { OT(x0), OT(x1), OT(x2), OT(x3), OT(x4); }
 126 template <typename T0, typename T1, typename T2, typename T3, typename T4, typename T5> inline void OT(const T0 &x0, const T1 &x1, const T2 &x2, const T3 &x3, const T4 &x4, const T5 &x5) { OT(x0), OT(x1), OT(x2), OT(x3), OT(x4), OT(x5); }
 127 template <typename T0, typename T1, typename T2, typename T3, typename T4, typename T5, typename T6> inline void OT(const T0 &x0, const T1 &x1, const T2 &x2, const T3 &x3, const T4 &x4, const T5 &x5, const T6 &x6) { OT(x0), OT(x1), OT(x2), OT(x3), OT(x4), OT(x5), OT(x6); }
 128 inline char& RC(char &a, char &b) { RC(a), RC(b); return a; }
 129 inline char& RC(char &a, char &b, char &c) { RC(a), RC(b), RC(c); return a; }
 130 inline char& RC(char &a, char &b, char &c, char &d) { RC(a), RC(b), RC(c), RC(d); return a; }
 131 inline char& RC(char &a, char &b, char &c, char &d, char &e) { RC(a), RC(b), RC(c), RC(d), RC(e); return a; }
 132 inline char& RC(char &a, char &b, char &c, char &d, char &e, char &f) { RC(a), RC(b), RC(c), RC(d), RC(e), RC(f); return a; }
 133 inline char& RC(char &a, char &b, char &c, char &d, char &e, char &f, char &g) { RC(a), RC(b), RC(c), RC(d), RC(e), RC(f), RC(g); return a; }
 134 inline double& RF(double &a, double &b) { RF(a), RF(b); return a; }
 135 inline double& RF(double &a, double &b, double &c) { RF(a), RF(b), RF(c); return a; }
 136 inline double& RF(double &a, double &b, double &c, double &d) { RF(a), RF(b), RF(c), RF(d); return a; }
 137 inline double& RF(double &a, double &b, double &c, double &d, double &e) { RF(a), RF(b), RF(c), RF(d), RF(e); return a; }
 138 inline double& RF(double &a, double &b, double &c, double &d, double &e, double &f) { RF(a), RF(b), RF(c), RF(d), RF(e), RF(f); return a; }
 139 inline double& RF(double &a, double &b, double &c, double &d, double &e, double &f, double &g) { RF(a), RF(b), RF(c), RF(d), RF(e), RF(f), RF(g); return a; }
 140 inline void RS(char *s1, char *s2) { RS(s1), RS(s2); }
 141 inline void RS(char *s1, char *s2, char *s3) { RS(s1), RS(s2), RS(s3); }
 142
 143 template <typename T> inline void RST(T &A) { memset(A, 0, sizeof(A)); }
 144 template <typename T0, typename T1> inline void RST(T0 &A0, T1 &A1) { RST(A0), RST(A1); }
 145 template <typename T0, typename T1, typename T2> inline void RST(T0 &A0, T1 &A1, T2 &A2) { RST(A0), RST(A1), RST(A2); }
 146 template <typename T0, typename T1, typename T2, typename T3> inline void RST(T0 &A0, T1 &A1, T2 &A2, T3 &A3) { RST(A0), RST(A1), RST(A2), RST(A3); }
 147 template <typename T0, typename T1, typename T2, typename T3, typename T4> inline void RST(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4) { RST(A0), RST(A1), RST(A2), RST(A3), RST(A4); }
 148 template <typename T0, typename T1, typename T2, typename T3, typename T4, typename T5> inline void RST(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5) { RST(A0), RST(A1), RST(A2), RST(A3), RST(A4), RST(A5); }
 149 template <typename T0, typename T1, typename T2, typename T3, typename T4, typename T5, typename T6> inline void RST(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5, T6 &A6) { RST(A0), RST(A1), RST(A2), RST(A3), RST(A4), RST(A5), RST(A6); }
 150 template <typename T> inline void FILL(T &A, int x) { memset(A, x, sizeof(A)); }
 151 template <typename T0, typename T1> inline void FILL(T0 &A0, T1 &A1, int x) { FILL(A0, x), FILL(A1, x); }
 152 template <typename T0, typename T1, typename T2> inline void FILL(T0 &A0, T1 &A1, T2 &A2, int x) { FILL(A0, x), FILL(A1, x), FILL(A2, x); }
 153 template <typename T0, typename T1, typename T2, typename T3> inline void FILL(T0 &A0, T1 &A1, T2 &A2, T3 &A3, int x) { FILL(A0, x), FILL(A1, x), FILL(A2, x), FILL(A3, x); }
 154 template <typename T0, typename T1, typename T2, typename T3, typename T4> inline void FILL(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, int x) { FILL(A0, x), FILL(A1, x), FILL(A2, x), FILL(A3, x), FILL(A4, x); }
 155 template <typename T0, typename T1, typename T2, typename T3, typename T4, typename T5> inline void FILL(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5, int x) { FILL(A0, x), FILL(A1, x), FILL(A2, x), FILL(A3, x), FILL(A4, x), FILL(A5, x); }
 156 template <typename T0, typename T1, typename T2, typename T3, typename T4, typename T5, typename T6> inline void FILL(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5, T6 &A6, int x) { FILL(A0, x), FILL(A1, x), FILL(A2, x), FILL(A3, x), FILL(A4, x), FILL(A5, x), FILL(A6, x); }
 157 template <typename T> inline void CLR(std::priority_queue <T, std::vector <T> , std::less <T> > &q) { while (!q.empty()) q.pop(); }
 158 template <typename T> inline void CLR(std::priority_queue <T, std::vector <T> , std::greater <T> > &q) { while (!q.empty()) q.pop(); }
 159 template <typename T> inline void CLR(T &A) { A.clear(); }
 160 template <typename T0, typename T1> inline void CLR(T0 &A0, T1 &A1) { CLR(A0), CLR(A1); }
 161 template <typename T0, typename T1, typename T2> inline void CLR(T0 &A0, T1 &A1, T2 &A2) { CLR(A0), CLR(A1), CLR(A2); }
 162 template <typename T0, typename T1, typename T2, typename T3> inline void CLR(T0 &A0, T1 &A1, T2 &A2, T3 &A3) { CLR(A0), CLR(A1), CLR(A2), CLR(A3); }
 163 template <typename T0, typename T1, typename T2, typename T3, typename T4> inline void CLR(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4) { CLR(A0), CLR(A1), CLR(A2), CLR(A3), CLR(A4); }
 164 template <typename T0, typename T1, typename T2, typename T3, typename T4, typename T5> inline void CLR(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5) { CLR(A0), CLR(A1), CLR(A2), CLR(A3), CLR(A4), CLR(A5); }
 165 template <typename T0, typename T1, typename T2, typename T3, typename T4, typename T5, typename T6> inline void CLR(T0 &A0, T1 &A1, T2 &A2, T3 &A3, T4 &A4, T5 &A5, T6 &A6) { CLR(A0), CLR(A1), CLR(A2), CLR(A3), CLR(A4), CLR(A5), CLR(A6); }
 166 template <typename T> inline void CLR(T &A, int n) { REP(i, n) CLR(A[i]); }
 167
 168 template <typename T> inline void cmax(T &x, T ano) { if (!(ano < x)) x = ano; }
 169 template <typename T> inline void cmin(T &x, T ano) { if (ano < x) x = ano; }
 170 template <typename T> inline T sqr(T x) { return x * x; }
 171
 172 namespace BO {
 173
 174 inline bool _1(int x, int i) { return (bool)(x & 1 << i); }
 175 inline bool _1(int64 x, int i) { return (bool)(x & 1LL << i); }
 176 inline int64 _1(int i) { return 1LL << i; }
 177 inline int64 _U(int i) { return _1(i) - 1; }
 178 inline int reverse_bits(int x) {
 179   x = ((x >> 1) & 0x55555555) | ((x << 1) & 0xaaaaaaaa);
 180   x = ((x >> 2) & 0x33333333) | ((x << 2) & 0xcccccccc);
 181   x = ((x >> 4) & 0x0f0f0f0f) | ((x << 4) & 0xf0f0f0f0);
 182   x = ((x >> 8) & 0x00ff00ff) | ((x << 8) & 0xff00ff00);
 183   x = ((x >> 16) & 0x0000ffff) | ((x << 16) & 0xffff0000);
 184   return x;
 185 }
 186 inline int64 reverse_bits(int64 x) {
 187   x = ((x >> 1) & 0x5555555555555555LL) | ((x << 1) & 0xaaaaaaaaaaaaaaaaLL);
 188   x = ((x >> 2) & 0x3333333333333333LL) | ((x << 2) & 0xccccccccccccccccLL);
 189   x = ((x >> 4) & 0x0f0f0f0f0f0f0f0fLL) | ((x << 4) & 0xf0f0f0f0f0f0f0f0LL);
 190   x = ((x >> 8) & 0x00ff00ff00ff00ffLL) | ((x << 8) & 0xff00ff00ff00ff00LL);
 191   x = ((x >> 16) & 0x0000ffff0000ffffLL) | ((x << 16) & 0xffff0000ffff0000LL);
 192   x = ((x >> 32) & 0x00000000ffffffffLL) | ((x << 32) & 0xffffffff00000000LL);
 193   return x;
 194 }
 195 template <typename T> inline bool odd(T x) { return x & 1; }
 196 template <typename T> inline bool even(T x) { return !odd(x); }
 197 template <typename T> inline T low_bit(T x) { return x & (x ^ (x - 1)); }
 198 template <typename T> inline T high_bit(T x) { T p = low_bit(x); while (p != x) x -= p, p = low_bit(x); return p; }
 199 template <typename T> inline T cover_bit(T x) { T p = 1; while (p < x) p <<= 1; return p; }
 200 inline int low_idx(int x) { return __builtin_ffs(x); }
 201 inline int low_idx(int64 x) { return __builtin_ffsll(x); }
 202 inline int high_idx(int x) { return low_idx(reverse_bits(x)); }
 203 inline int high_idx(int64 x) { return low_idx(reverse_bits(x)); }
 204 inline int clz(int x) { return __builtin_clz(x); }
 205 inline int clz(int64 x) { return __builtin_clzll(x); }
 206 inline int ctz(int x) { return __builtin_ctz(x); }
 207 inline int ctz(int64 x) { return __builtin_ctzll(x); }
 208 inline int parity(int x) { return __builtin_parity(x); }
 209 inline int parity(int64 x) { return __builtin_parityll(x); }
 210 inline int lg2(int a) { return 31 - __builtin_clz(a); }
 211 inline int count_bits(int x) { return __builtin_popcount(x); }
 212 inline int count_bits(int64 x) { return __builtin_popcountll(x); }
 213
 214 } using namespace BO;
 215
 216 namespace NT {
 217
 218 inline void INC(int &a, int b) { a += b; if (a >= MOD) a -= MOD; }
 219 inline int sum(int a, int b) { a += b; if (a >= MOD) a -= MOD; return a; }
 220 inline void DEC(int &a, int b) { a -= b; if (a < 0) a += MOD; }
 221 inline int dif(int a, int b) { a -= b; if (a < 0) a += MOD; return a; }
 222 inline void MUL(int &a, int b) { a = (int64)a * b % MOD; }
 223 inline int pdt(int a, int b) { return (int64)a * b % MOD; }
 224 inline int sum(int a, int b, int c) { return sum(sum(a, b), c); }
 225 inline int sum(int a, int b, int c, int d) { return sum(sum(a, b), sum(c, d)); }
 226 inline int pdt(int a, int b, int c) { return pdt(pdt(a, b), c); }
 227 inline int pdt(int a, int b, int c, int d) { return pdt(pdt(pdt(a, b), c), d); }
 228
 229 template <typename T>
 230 inline T pow(T a, int64 b) {
 231   T c(1);
 232   while (b) {
 233     if (b & 1) c *= a;
 234     a *= a, b >>= 1;
 235   }
 236   return c;
 237 }
 238
 239 inline int _I(int b) {
 240   int a = MOD, x1 = 0, x2 = 1, q;
 241   while (true) {
 242     q = a / b, a %= b;
 243     if (!a) return (x2 + MOD) % MOD;
 244     DEC(x1, pdt(q, x2));
 245     q = b / a, b %= a;
 246     if (!b) return (x1 + MOD) % MOD;
 247     DEC(x2, pdt(q, x1));
 248   }
 249 }
 250
 251 inline void DIV(int &a, int b) { MUL(a, _I(b)); }
 252 inline int qtt(int a, int b) { return pdt(a, _I(b)); }
 253
 254 inline int phi(int n) {
 255   int res = n;
 256   for (int i = 2; sqr(i) <= n; ++i) {
 257     if (!(n % i)) {
 258       DEC(res, qtt(res, i));
 259       do { n /= i; } while(!(n % i));
 260     }
 261   }
 262   if (n != 1) DEC(res, qtt(res, n));
 263   return res;
 264 }
 265
 266 template <typename T>
 267 T gcd(T a, T b) {
 268   T r;
 269   do {
 270     r = a % b;
 271     a = b, b = r;
 272   } while (r);
 273   return a;
 274 }
 275
 276 } using namespace NT;
 277
 278 namespace RANDOM {
 279
 280 inline uint rand16() { return ((bool)(rand() & 1) << 15) | rand(); }
 281 inline uint rand32() { return (rand16() << 16) | rand16(); }
 282 inline uint64 rand64() { return ((int64)rand32() << 32) | rand32(); }
 283 inline uint64 random(int64 l, int64 r) { return rand64() % (r - l) + l; }
 284 inline uint dice() { return random(1, 6); }
 285 bool coin() { return rand() & 1; }
 286
 287 } using namespace RANDOM;
 288
 289 namespace CLOCK {
 290
 291 double s0, s1, rd, T;
 292 inline double getTime() {
 293 #ifdef LOCAL
 294   return 1.0 * clock() / CLOCKS_PER_SEC;
 295 #else
 296   timeval tv;
 297   gettimeofday(&tv, 0);
 298   return tv.tv_sec + tv.tv_usec * 1e-6;
 299 #endif
 300 }
 301 inline double elapsed() { return getTime() - s0; }
 302
 303 } //using namespace CLOCK;
 304
 305 template <typename T>
 306 inline T &RD(T &x) {
 307   static char c;
 308   static bool flag;
 309   flag = false;
 310   for (c = getchar(); !isdigit(c) && c != '-'; c = getchar()) {}
 311   if (c == '-') flag = true, c = RC();
 312   x = c - '0';
 313   for (c = getchar(); isdigit(c); c = getchar()) x = x * 10 + c - '0';
 314   if (flag) x = -x;
 315   return x;
 316 }
 317
 318 template <typename T> inline void OT(const T& x) {
 319   //printf("%lld\n", x);
 320   printf("%d\n", x);
 321   //printf("%.2lf\n", x);
 322   //std::cout << x << std::endl;
 323 }
 324 /** end of template **/
 325
 326 /* -------------------------------------------------------------------------- */
 327
 328 const int N = 500000 + 10;
 329
 330 int n;
 331 char s[N / 2];
 332
 333 struct node {
 334   node *next[26], *pre;
 335   int cnt, len;
 336 } buffer[N], *init = buffer, *top = init;
 337
 338 inline void append(char ch) {
 339   ch -= 'a';
 340   static node *last = init;
 341   node *p = last, *np = ++top;
 342   np->len = p->len + 1;
 343   for (; p && !p->next[ch]; p = p->pre) p->next[ch] = np;
 344   if (!p) {
 345     np->pre = init;
 346   } else {
 347     node *q = p->next[ch];
 348     if (q->len == p->len + 1) {
 349       np->pre = q;
 350     } else {
 351       node *nq = ++top;
 352       *nq = *q;
 353       nq->len = p->len + 1;
 354       q->pre = np->pre = nq;
 355       for (; p && p->next[ch] == q; p = p->pre) p->next[ch] = nq;
 356     }
 357   }
 358   last = np;
 359 }
 360
 361 int main() {
 362 #ifndef ONLINE_JUDGE
 363   freopen("in.txt", "r", stdin);
 364 #endif
 365   RS(s);
 366   int n = strlen(s);
 367   REP_S(it, s) append(*it);
 368   node *p = init;
 369   REP_S(it, s) (p = p->next[*it - 'a'])->cnt++;
 370   static int f[N], tmp[N];
 371   static node *q[N];
 372   for (node *it = init; it <= top; ++it) tmp[it->len]++;
 373   REP_1(i, n) tmp[i] += tmp[i - 1];
 374   for (node *it = init; it <= top; ++it) q[--tmp[it->len]] = it;
 375   DWN_1(i, top - buffer, 1) {
 376     cmax(f[q[i]->len], q[i]->cnt);
 377     q[i]->pre->cnt += q[i]->cnt;
 378   }
 379   DWN(i, n, 1) cmax(f[i], f[i + 1]);
 380   REP_1(i, n) OT(f[i]);
 381   return 0;
 382 }