Artifact 24b4786c5875bcf17e6190dc9d122a18b12f0c95:
0000: 2f 2f 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d //--------------
0010: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0020: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0030: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 0a ---------------.
0040: 2f 2f 20 53 75 66 66 69 78 20 41 72 72 61 79 0a // Suffix Array.
0050: 2f 2f 20 20 20 4f 28 4e 20 6c 6f 67 20 4e 29 20 // O(N log N)
0060: 63 6f 6e 73 74 72 75 63 74 69 6f 6e 20 62 79 20 construction by
0070: 4c 61 72 73 73 6f 6e 2d 53 61 64 61 6b 61 6e 65 Larsson-Sadakane
0080: 0a 2f 2f 20 20 20 20 66 72 6f 6d 20 68 74 74 70 .// from http
0090: 3a 2f 2f 77 77 77 2e 70 72 65 66 69 65 6c 64 2e ://www.prefield.
00a0: 63 6f 6d 2f 61 6c 67 6f 72 69 74 68 6d 2f 73 74 com/algorithm/st
00b0: 72 69 6e 67 2f 73 75 66 66 69 78 5f 61 72 72 61 ring/suffix_arra
00c0: 79 2e 68 74 6d 6c 0a 2f 2f 0a 2f 2f 20 63 6f 6d y.html.//.// com
00d0: 70 75 74 65 5f 73 75 66 66 69 78 5f 61 72 72 61 pute_suffix_arra
00e0: 79 28 22 62 61 63 61 22 29 0a 2f 2f 20 20 20 3d y("baca").// =
00f0: 20 7b 22 61 63 61 22 20 3c 20 22 61 24 22 20 3c {"aca" < "a$" <
0100: 20 22 62 61 63 61 22 20 3c 20 22 63 61 22 7d 20 "baca" < "ca"}
0110: 3d 20 7b 31 2c 33 2c 30 2c 32 7d 0a 2f 2f 20 20 = {1,3,0,2}.//
0120: 20 45 4f 53 20 69 73 20 73 65 74 20 74 6f 20 62 EOS is set to b
0130: 65 20 74 68 65 20 6c 61 72 67 65 73 74 20 73 79 e the largest sy
0140: 6d 62 6f 6c 20 28 69 6e 20 53 61 43 6f 6d 70 3a mbol (in SaComp:
0150: 20 30 78 37 66 66 66 66 66 66 66 29 2e 0a 2f 2f 0x7fffffff)..//
0160: 0a 2f 2f 20 6c 63 70 5b 30 5d 20 3d 20 2d 31 0a .// lcp[0] = -1.
0170: 2f 2f 20 6c 63 70 5b 69 5d 20 3d 20 6c 63 70 20 // lcp[i] = lcp
0180: 6f 66 20 73 74 72 5b 73 61 5b 69 2d 31 5d 2e 2e of str[sa[i-1]..
0190: 24 5d 20 61 6e 64 20 73 74 72 5b 73 61 5b 69 5d $] and str[sa[i]
01a0: 2e 2e 24 5d 2e 0a 2f 2f 0a 2f 2f 20 56 65 72 69 ..$]..//.// Veri
01b0: 66 69 65 64 20 62 79 0a 2f 2f 20 20 20 2d 20 43 fied by.// - C
01c0: 6f 64 65 66 6f 72 63 65 73 20 31 32 39 20 44 69 odeforces 129 Di
01d0: 76 31 20 45 0a 2f 2f 2d 2d 2d 2d 2d 2d 2d 2d 2d v1 E.//---------
01e0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
01f0: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0200: 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d 2d ----------------
0210: 2d 2d 2d 2d 0a 0a 73 74 72 75 63 74 20 53 61 43 ----..struct SaC
0220: 6f 6d 70 20 7b 0a 09 63 6f 6e 73 74 20 69 6e 74 omp {..const int
0230: 20 73 70 2c 20 2a 73 72 2c 20 73 72 6c 65 6e 3b sp, *sr, srlen;
0240: 0a 09 53 61 43 6f 6d 70 28 69 6e 74 20 73 70 2c ..SaComp(int sp,
0250: 20 63 6f 6e 73 74 20 76 65 63 74 6f 72 3c 69 6e const vector<in
0260: 74 3e 26 20 73 72 29 20 3a 20 73 70 28 73 70 29 t>& sr) : sp(sp)
0270: 2c 20 73 72 28 26 73 72 5b 30 5d 29 2c 20 73 72 , sr(&sr[0]), sr
0280: 6c 65 6e 28 73 72 2e 73 69 7a 65 28 29 29 20 7b len(sr.size()) {
0290: 7d 0a 09 62 6f 6f 6c 20 6f 70 65 72 61 74 6f 72 }..bool operator
02a0: 28 29 28 69 6e 74 20 61 2c 20 69 6e 74 20 62 29 ()(int a, int b)
02b0: 20 63 6f 6e 73 74 0a 09 20 20 7b 20 72 65 74 75 const.. { retu
02c0: 72 6e 20 6d 61 6b 65 5f 70 61 69 72 28 73 72 5b rn make_pair(sr[
02d0: 61 5d 2c 20 61 2b 73 70 3c 73 72 6c 65 6e 3f 73 a], a+sp<srlen?s
02e0: 72 5b 61 2b 73 70 5d 3a 30 78 37 66 66 66 66 66 r[a+sp]:0x7fffff
02f0: 66 66 29 0a 09 20 20 20 20 20 20 20 20 20 3c 20 ff).. <
0300: 6d 61 6b 65 5f 70 61 69 72 28 73 72 5b 62 5d 2c make_pair(sr[b],
0310: 20 62 2b 73 70 3c 73 72 6c 65 6e 3f 73 72 5b 62 b+sp<srlen?sr[b
0320: 2b 73 70 5d 3a 30 78 37 66 66 66 66 66 66 66 29 +sp]:0x7fffffff)
0330: 3b 20 7d 0a 7d 3b 0a 0a 74 65 6d 70 6c 61 74 65 ; }.};..template
0340: 3c 74 79 70 65 6e 61 6d 65 20 52 61 6e 49 74 3e <typename RanIt>
0350: 0a 76 65 63 74 6f 72 3c 69 6e 74 3e 20 63 6f 6d .vector<int> com
0360: 70 75 74 65 5f 73 75 66 66 69 78 5f 61 72 72 61 pute_suffix_arra
0370: 79 28 52 61 6e 49 74 20 62 65 67 2c 20 52 61 6e y(RanIt beg, Ran
0380: 49 74 20 65 6e 64 29 0a 7b 0a 09 63 6f 6e 73 74 It end).{..const
0390: 20 69 6e 74 20 4e 20 3d 20 65 6e 64 20 2d 20 62 int N = end - b
03a0: 65 67 3b 0a 0a 09 76 65 63 74 6f 72 3c 69 6e 74 eg;...vector<int
03b0: 3e 20 73 61 28 4e 29 3b 0a 09 76 65 63 74 6f 72 > sa(N);..vector
03c0: 3c 69 6e 74 3e 20 73 6f 72 74 5f 72 61 6e 6b 28 <int> sort_rank(
03d0: 62 65 67 2c 20 65 6e 64 29 3b 0a 09 66 6f 72 28 beg, end);..for(
03e0: 69 6e 74 20 69 3d 30 3b 20 69 3c 4e 3b 20 2b 2b int i=0; i<N; ++
03f0: 69 29 0a 09 09 73 61 5b 69 5d 20 3d 20 69 3b 0a i)...sa[i] = i;.
0400: 0a 09 73 6f 72 74 28 73 61 2e 62 65 67 69 6e 28 ..sort(sa.begin(
0410: 29 2c 20 73 61 2e 65 6e 64 28 29 2c 20 53 61 43 ), sa.end(), SaC
0420: 6f 6d 70 28 30 2c 20 73 6f 72 74 5f 72 61 6e 6b omp(0, sort_rank
0430: 29 29 3b 0a 09 66 6f 72 28 69 6e 74 20 73 6f 72 ));..for(int sor
0440: 74 65 64 5f 70 72 65 66 69 78 3d 31 3b 20 73 6f ted_prefix=1; so
0450: 72 74 65 64 5f 70 72 65 66 69 78 3c 4e 3b 20 73 rted_prefix<N; s
0460: 6f 72 74 65 64 5f 70 72 65 66 69 78 2a 3d 32 29 orted_prefix*=2)
0470: 0a 09 7b 0a 09 09 53 61 43 6f 6d 70 20 63 6d 70 ..{...SaComp cmp
0480: 28 73 6f 72 74 65 64 5f 70 72 65 66 69 78 2c 20 (sorted_prefix,
0490: 73 6f 72 74 5f 72 61 6e 6b 29 3b 0a 09 09 73 6f sort_rank);...so
04a0: 72 74 28 73 61 2e 62 65 67 69 6e 28 29 2c 20 73 rt(sa.begin(), s
04b0: 61 2e 65 6e 64 28 29 2c 20 63 6d 70 29 3b 0a 0a a.end(), cmp);..
04c0: 09 09 76 65 63 74 6f 72 3c 69 6e 74 3e 20 62 6c ..vector<int> bl
04d0: 6f 63 6b 5f 69 64 28 4e 29 3b 0a 09 09 66 6f 72 ock_id(N);...for
04e0: 28 69 6e 74 20 69 3d 31 3b 20 69 3c 4e 3b 20 2b (int i=1; i<N; +
04f0: 2b 69 29 0a 09 09 09 62 6c 6f 63 6b 5f 69 64 5b +i)....block_id[
0500: 69 5d 20 3d 20 62 6c 6f 63 6b 5f 69 64 5b 69 2d i] = block_id[i-
0510: 31 5d 20 2b 20 28 63 6d 70 28 73 61 5b 69 2d 31 1] + (cmp(sa[i-1
0520: 5d 2c 20 73 61 5b 69 5d 29 20 3f 20 31 20 3a 20 ], sa[i]) ? 1 :
0530: 30 29 3b 0a 09 09 66 6f 72 28 69 6e 74 20 69 3d 0);...for(int i=
0540: 30 3b 20 69 3c 4e 3b 20 2b 2b 69 29 0a 09 09 09 0; i<N; ++i)....
0550: 73 6f 72 74 5f 72 61 6e 6b 5b 73 61 5b 69 5d 5d sort_rank[sa[i]]
0560: 20 3d 20 62 6c 6f 63 6b 5f 69 64 5b 69 5d 3b 0a = block_id[i];.
0570: 09 7d 0a 09 72 65 74 75 72 6e 20 73 61 3b 0a 7d .}..return sa;.}
0580: 0a 0a 76 65 63 74 6f 72 3c 69 6e 74 3e 20 69 6e ..vector<int> in
0590: 76 5f 73 61 28 63 6f 6e 73 74 20 76 65 63 74 6f v_sa(const vecto
05a0: 72 3c 69 6e 74 3e 26 20 73 61 29 0a 7b 0a 09 76 r<int>& sa).{..v
05b0: 65 63 74 6f 72 3c 69 6e 74 3e 20 69 73 61 28 73 ector<int> isa(s
05c0: 61 2e 73 69 7a 65 28 29 29 3b 0a 09 66 6f 72 28 a.size());..for(
05d0: 69 6e 74 20 69 3d 30 3b 20 69 3c 73 61 2e 73 69 int i=0; i<sa.si
05e0: 7a 65 28 29 3b 20 2b 2b 69 29 0a 09 09 69 73 61 ze(); ++i)...isa
05f0: 5b 73 61 5b 69 5d 5d 20 3d 20 69 3b 0a 09 72 65 [sa[i]] = i;..re
0600: 74 75 72 6e 20 69 73 61 3b 0a 7d 0a 0a 74 65 6d turn isa;.}..tem
0610: 70 6c 61 74 65 3c 74 79 70 65 6e 61 6d 65 20 52 plate<typename R
0620: 61 6e 49 74 65 3e 0a 76 65 63 74 6f 72 3c 69 6e anIte>.vector<in
0630: 74 3e 20 6c 6f 6e 67 65 73 74 5f 63 6f 6d 6d 6f t> longest_commo
0640: 6e 5f 70 72 65 66 69 78 28 52 61 6e 49 74 65 20 n_prefix(RanIte
0650: 62 65 67 2c 20 52 61 6e 49 74 65 20 65 6e 64 2c beg, RanIte end,
0660: 20 63 6f 6e 73 74 20 76 65 63 74 6f 72 3c 69 6e const vector<in
0670: 74 3e 26 20 73 61 29 0a 7b 0a 09 63 6f 6e 73 74 t>& sa).{..const
0680: 20 69 6e 74 20 4e 20 3d 20 73 61 2e 73 69 7a 65 int N = sa.size
0690: 28 29 3b 0a 09 76 65 63 74 6f 72 3c 69 6e 74 3e ();..vector<int>
06a0: 20 6c 63 70 28 4e 29 3b 0a 09 76 65 63 74 6f 72 lcp(N);..vector
06b0: 3c 69 6e 74 3e 20 69 6e 76 20 3d 20 69 6e 76 5f <int> inv = inv_
06c0: 73 61 28 73 61 29 3b 0a 0a 09 69 6e 74 20 6c 65 sa(sa);...int le
06d0: 6e 20 3d 20 30 3b 0a 09 66 6f 72 28 69 6e 74 20 n = 0;..for(int
06e0: 69 3d 30 3b 20 69 3c 4e 3b 20 2b 2b 69 29 20 7b i=0; i<N; ++i) {
06f0: 0a 09 09 69 6e 74 20 73 61 5f 69 64 78 20 3d 20 ...int sa_idx =
0700: 69 6e 76 5b 69 5d 3b 0a 09 09 69 66 28 20 73 61 inv[i];...if( sa
0710: 5f 69 64 78 20 3d 3d 20 30 20 29 0a 09 09 09 6c _idx == 0 )....l
0720: 63 70 5b 73 61 5f 69 64 78 5d 20 3d 20 2d 31 3b cp[sa_idx] = -1;
0730: 0a 09 09 65 6c 73 65 20 7b 0a 09 09 09 66 6f 72 ...else {....for
0740: 28 69 6e 74 20 6b 3d 73 61 5b 73 61 5f 69 64 78 (int k=sa[sa_idx
0750: 2d 31 5d 3b 20 69 2b 6c 65 6e 3c 4e 20 26 26 20 -1]; i+len<N &&
0760: 6b 2b 6c 65 6e 3c 4e 20 26 26 20 2a 28 62 65 67 k+len<N && *(beg
0770: 2b 69 2b 6c 65 6e 29 3d 3d 2a 28 62 65 67 2b 6b +i+len)==*(beg+k
0780: 2b 6c 65 6e 29 3b 29 0a 09 09 09 09 2b 2b 6c 65 +len);).....++le
0790: 6e 3b 0a 09 09 09 6c 63 70 5b 73 61 5f 69 64 78 n;....lcp[sa_idx
07a0: 5d 20 3d 20 6c 65 6e 3b 0a 09 09 7d 0a 09 09 69 ] = len;...}...i
07b0: 66 28 6c 65 6e 29 20 2d 2d 6c 65 6e 3b 0a 09 7d f(len) --len;..}
07c0: 0a 09 72 65 74 75 72 6e 20 6c 63 70 3b 0a 7d 0a ..return lcp;.}.