This documentation is automatically generated by online-judge-tools/verification-helper
# ac-library.cr by hakatashi https://github.com/google/ac-library.cr # # Copyright 2023 Google LLC # # Licensed under the Apache License, Version 2.0 (the "License"); # you may not use this file except in compliance with the License. # You may obtain a copy of the License at # # https://www.apache.org/licenses/LICENSE-2.0 # # Unless required by applicable law or agreed to in writing, software # distributed under the License is distributed on an "AS IS" BASIS, # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. # See the License for the specific language governing permissions and # limitations under the License. require "../src/string.cr" require "spec" describe "String" do describe ".suffix_array" do it "returns suffix array in O(n)" do AtCoder::String.suffix_array("abcbcba").should eq [6, 0, 5, 3, 1, 4, 2] AtCoder::String.suffix_array("mississippi").should eq [10, 7, 4, 1, 0, 9, 8, 6, 3, 5, 2] AtCoder::String.suffix_array("ababacaca").should eq [8, 0, 2, 6, 4, 1, 3, 7, 5] AtCoder::String.suffix_array("aaaaa").should eq [4, 3, 2, 1, 0] end it "returns suffix array in O(n log(n))" do AtCoder::String.suffix_array([1_i64, 2_i64, 3_i64, 2_i64, 3_i64, 2_i64, 1_i64]).should eq [6, 0, 5, 3, 1, 4, 2] AtCoder::String.suffix_array([2**12, 2**8, 2**18, 2**18, 2**8, 2**18, 2**18, 2**8, 2**15, 2**15, 2**8]).should eq [10, 7, 4, 1, 0, 9, 8, 6, 3, 5, 2] AtCoder::String.suffix_array([1, 2, 1, 2, 1, 3, 1, 3, 1]).should eq [8, 0, 2, 6, 4, 1, 3, 7, 5] AtCoder::String.suffix_array([10_i64**18, 10_i64**18, 10_i64**18, 10_i64**18, 10_i64**18]).should eq [4, 3, 2, 1, 0] end it "returns suffix array in O(n + uppper)" do AtCoder::String.suffix_array([1, 2, 3, 2, 3, 2, 1], 3).should eq [6, 0, 5, 3, 1, 4, 2] AtCoder::String.suffix_array([2**12, 2**8, 2**18, 2**18, 2**8, 2**18, 2**18, 2**8, 2**15, 2**15, 2**8], 2**18).should eq [10, 7, 4, 1, 0, 9, 8, 6, 3, 5, 2] AtCoder::String.suffix_array([1, 2, 1, 2, 1, 3, 1, 3, 1], 3).should eq [8, 0, 2, 6, 4, 1, 3, 7, 5] AtCoder::String.suffix_array([0, 0, 0, 0, 0], 10**8).should eq [4, 3, 2, 1, 0] end end describe ".lcp_array" do it "returns lcp_array" do AtCoder::String.lcp_array("abcbcba", AtCoder::String.suffix_array("abcbcba")).should eq [1, 0, 1, 3, 0, 2] AtCoder::String.lcp_array("mississippi", AtCoder::String.suffix_array("mississippi")).should eq [1, 1, 4, 0, 0, 1, 0, 2, 1, 3] AtCoder::String.lcp_array("ababacaca", AtCoder::String.suffix_array("ababacaca")).should eq [1, 3, 1, 3, 0, 2, 0, 2] AtCoder::String.lcp_array("aaaaa", AtCoder::String.suffix_array("aaaaa")).should eq [1, 2, 3, 4] AtCoder::String.lcp_array([1, 2, 3, 2, 3, 2, 1], AtCoder::String.suffix_array([1, 2, 3, 2, 3, 2, 1])).should eq [1, 0, 1, 3, 0, 2] AtCoder::String.lcp_array([12, 8, 18, 18, 8, 18, 18, 8, 15, 15, 8], AtCoder::String.suffix_array([12, 8, 18, 18, 8, 18, 18, 8, 15, 15, 8])).should eq [1, 1, 4, 0, 0, 1, 0, 2, 1, 3] AtCoder::String.lcp_array([1, 2, 1, 2, 1, 3, 1, 3, 1], AtCoder::String.suffix_array([1, 2, 1, 2, 1, 3, 1, 3, 1])).should eq [1, 3, 1, 3, 0, 2, 0, 2] AtCoder::String.lcp_array([1, 1, 1, 1, 1], AtCoder::String.suffix_array([1, 1, 1, 1, 1])).should eq [1, 2, 3, 4] end end describe ".z_algorithm" do it "returns empty array if input sequence is empty" do AtCoder::String.z_algorithm([] of Int32).should eq [] of Int32 AtCoder::String.z_algorithm("").should eq [] of Int32 end it "returns the sequence of length n, such that the i-th element is the length of the LCP (Longest Common Prefix) of s[0...n] and s[i...n]." do AtCoder::String.z_algorithm("abcbcba").should eq [7, 0, 0, 0, 0, 0, 1] AtCoder::String.z_algorithm("mississippi").should eq [11, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] AtCoder::String.z_algorithm("ababacaca").should eq [9, 0, 3, 0, 1, 0, 1, 0, 1] AtCoder::String.z_algorithm("aaaaa").should eq [5, 4, 3, 2, 1] AtCoder::String.z_algorithm([1, 2, 3, 2, 3, 2, 1]).should eq [7, 0, 0, 0, 0, 0, 1] AtCoder::String.z_algorithm([1, 2, 3, 3, 2, 3, 3, 2, 4, 4, 2]).should eq [11, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] AtCoder::String.z_algorithm([1, 2, 1, 2, 1, 3, 1, 3, 1]).should eq [9, 0, 3, 0, 1, 0, 1, 0, 1] AtCoder::String.z_algorithm([1, 1, 1, 1, 1]).should eq [5, 4, 3, 2, 1] end end end
# ac-library.cr by hakatashi https://github.com/google/ac-library.cr # # Copyright 2023 Google LLC # # Licensed under the Apache License, Version 2.0 (the "License"); # you may not use this file except in compliance with the License. # You may obtain a copy of the License at # # https://www.apache.org/licenses/LICENSE-2.0 # # Unless required by applicable law or agreed to in writing, software # distributed under the License is distributed on an "AS IS" BASIS, # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. # See the License for the specific language governing permissions and # limitations under the License. # require "../src/string.cr" # ac-library.cr by hakatashi https://github.com/google/ac-library.cr # # Copyright 2023 Google LLC # # Licensed under the Apache License, Version 2.0 (the "License"); # you may not use this file except in compliance with the License. # You may obtain a copy of the License at # # https://www.apache.org/licenses/LICENSE-2.0 # # Unless required by applicable law or agreed to in writing, software # distributed under the License is distributed on an "AS IS" BASIS, # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. # See the License for the specific language governing permissions and # limitations under the License. module AtCoder module String private SA_THRESHOLD_NAIVE = 10 private SA_THRESHOLD_DOUBLING = 40 private def self.sa_naive(s) n = s.size sa = (0...n).to_a.sort { |l, r| next 1 if l == r res = nil while l < n && r < n if s[l] != s[r] res = s[l] <=> s[r] break end l += 1 r += 1 end res ? res : (l == n ? -1 : 1) } sa end private def self.sa_doubling(s) n = s.size sa = (0...n).to_a rank = s.clone tmp = [0] * n k = 1 while k < n cmp = ->(x : Int32, y : Int32) { return rank[x] <=> rank[y] if rank[x] != rank[y] rx = x + k < n ? rank[x + k] : -1 ry = y + k < n ? rank[y + k] : -1 rx <=> ry } sa.sort! { |a, b| cmp.call(a, b) } tmp[sa[0]] = 0 (1...n).each do |i| tmp[sa[i]] = tmp[sa[i - 1]] + (cmp.call(sa[i - 1], sa[i]) == -1 ? 1 : 0) end tmp, rank = rank, tmp k *= 2 end sa end # ameba:disable Metrics/CyclomaticComplexity private def self.sa_is(s, upper) n = s.size case n when .==(0) return [] of Int32 when .==(1) return [0] when .==(2) return s[0] < s[1] ? [0, 1] : [1, 0] when .<(SA_THRESHOLD_NAIVE) return sa_naive(s) when .<(SA_THRESHOLD_DOUBLING) return sa_doubling(s) end sa = [0] * n ls = [false] * n (n - 2).downto(0) do |i| ls[i] = s[i] == s[i + 1] ? ls[i + 1] : s[i] < s[i + 1] end sum_l = [0] * (upper + 1) sum_s = [0] * (upper + 1) n.times do |i| if ls[i] sum_l[s[i] + 1] += 1 else sum_s[s[i]] += 1 end end (0..upper).each do |i| sum_s[i] += sum_l[i] sum_l[i + 1] += sum_s[i] if i < upper end induce = ->(lms : Array(Int32)) do sa = [-1] * n buffer = sum_s.clone lms.each do |d| next if d == n sa[buffer[s[d]]] = d buffer[s[d]] += 1 end buffer = sum_l.clone sa[buffer[s[n - 1]]] = n - 1 buffer[s[n - 1]] += 1 n.times do |i| v = sa[i] if v >= 1 && !ls[v - 1] sa[buffer[s[v - 1]]] = v - 1 buffer[s[v - 1]] += 1 end end buffer = sum_l.clone (n - 1).downto(0) do |i| v = sa[i] if v >= 1 && ls[v - 1] buffer[s[v - 1] + 1] -= 1 sa[buffer[s[v - 1] + 1]] = v - 1 end end end lms_map = [-1] * (n + 1) m = 0 (1...n).each do |i| if !ls[i - 1] && ls[i] lms_map[i] = m m += 1 end end lms = Array(Int32).new(m) (1...n).each do |i| if !ls[i - 1] && ls[i] lms << i end end induce.call(lms) return sa if m == 0 sorted_lms = Array(Int32).new(m) sa.each do |v| sorted_lms << v if lms_map[v] != -1 end rec_s = [0] * m rec_upper = 0 rec_s[lms_map[sorted_lms[0]]] = 0 (1...m).each do |i| l = sorted_lms[i - 1] r = sorted_lms[i] end_l = (lms_map[l] + 1 < m) ? lms[lms_map[l] + 1] : n end_r = (lms_map[r] + 1 < m) ? lms[lms_map[r] + 1] : n same = true if end_l - l != end_r - r same = false else while l < end_l break if s[l] != s[r] l += 1 r += 1 end same = false if l == n || s[l] != s[r] end rec_upper += 1 unless same rec_s[lms_map[sorted_lms[i]]] = rec_upper end rec_sa = sa_is(rec_s, rec_upper) m.times do |i| sorted_lms[i] = lms[rec_sa[i]] end induce.call(sorted_lms) sa end # returns suffix array in O(n + upper) def self.suffix_array(sequence : Indexable(Int32), upper) sa_is(sequence, upper) end # returns suffix array in O(n log(n)) def self.suffix_array(sequence : Indexable) n = sequence.size indices = (0...n).to_a.sort { |l, r| sequence[l] <=> sequence[r] } s2 = [0] * n now = 0 n.times do |i| now += 1 if i > 0 && sequence[indices[i - 1]] != sequence[indices[i]] s2[indices[i]] = now end upper = now sa_is(s2, upper) end # returns suffix array in O(n) def self.suffix_array(sequence : ::String) sa_is(sequence.bytes.map(&.to_i32), 255) end # returns lcp array in O(n) def self.lcp_array(sequence, sa) n = sequence.size rank = [0] * n sa.each_with_index { |e, i| rank[e] = i } lcp = [0] * (n - 1) h = 0 n.times do |i| h -= 1 if h > 0 next if rank[i] == 0 j = sa[rank[i] - 1] while j + h < n && i + h < n break if sequence[j + h] != sequence[i + h] h += 1 end lcp[rank[i] - 1] = h end lcp end # returns z array def self.z_algorithm(sequence) n = sequence.size return [] of Int32 if n == 0 z = [0] * n i, j = 1, 0 while i < n z[i] = (j + z[j] <= i) ? 0 : (j + z[j] - i < z[i - j] ? j + z[j] - i : z[i - j]) while i + z[i] < n && sequence[z[i]] == sequence[i + z[i]] z[i] += 1 end j = i if j + z[j] < i + z[i] i += 1 end z[0] = n z end end end require "spec" describe "String" do describe ".suffix_array" do it "returns suffix array in O(n)" do AtCoder::String.suffix_array("abcbcba").should eq [6, 0, 5, 3, 1, 4, 2] AtCoder::String.suffix_array("mississippi").should eq [10, 7, 4, 1, 0, 9, 8, 6, 3, 5, 2] AtCoder::String.suffix_array("ababacaca").should eq [8, 0, 2, 6, 4, 1, 3, 7, 5] AtCoder::String.suffix_array("aaaaa").should eq [4, 3, 2, 1, 0] end it "returns suffix array in O(n log(n))" do AtCoder::String.suffix_array([1_i64, 2_i64, 3_i64, 2_i64, 3_i64, 2_i64, 1_i64]).should eq [6, 0, 5, 3, 1, 4, 2] AtCoder::String.suffix_array([2**12, 2**8, 2**18, 2**18, 2**8, 2**18, 2**18, 2**8, 2**15, 2**15, 2**8]).should eq [10, 7, 4, 1, 0, 9, 8, 6, 3, 5, 2] AtCoder::String.suffix_array([1, 2, 1, 2, 1, 3, 1, 3, 1]).should eq [8, 0, 2, 6, 4, 1, 3, 7, 5] AtCoder::String.suffix_array([10_i64**18, 10_i64**18, 10_i64**18, 10_i64**18, 10_i64**18]).should eq [4, 3, 2, 1, 0] end it "returns suffix array in O(n + uppper)" do AtCoder::String.suffix_array([1, 2, 3, 2, 3, 2, 1], 3).should eq [6, 0, 5, 3, 1, 4, 2] AtCoder::String.suffix_array([2**12, 2**8, 2**18, 2**18, 2**8, 2**18, 2**18, 2**8, 2**15, 2**15, 2**8], 2**18).should eq [10, 7, 4, 1, 0, 9, 8, 6, 3, 5, 2] AtCoder::String.suffix_array([1, 2, 1, 2, 1, 3, 1, 3, 1], 3).should eq [8, 0, 2, 6, 4, 1, 3, 7, 5] AtCoder::String.suffix_array([0, 0, 0, 0, 0], 10**8).should eq [4, 3, 2, 1, 0] end end describe ".lcp_array" do it "returns lcp_array" do AtCoder::String.lcp_array("abcbcba", AtCoder::String.suffix_array("abcbcba")).should eq [1, 0, 1, 3, 0, 2] AtCoder::String.lcp_array("mississippi", AtCoder::String.suffix_array("mississippi")).should eq [1, 1, 4, 0, 0, 1, 0, 2, 1, 3] AtCoder::String.lcp_array("ababacaca", AtCoder::String.suffix_array("ababacaca")).should eq [1, 3, 1, 3, 0, 2, 0, 2] AtCoder::String.lcp_array("aaaaa", AtCoder::String.suffix_array("aaaaa")).should eq [1, 2, 3, 4] AtCoder::String.lcp_array([1, 2, 3, 2, 3, 2, 1], AtCoder::String.suffix_array([1, 2, 3, 2, 3, 2, 1])).should eq [1, 0, 1, 3, 0, 2] AtCoder::String.lcp_array([12, 8, 18, 18, 8, 18, 18, 8, 15, 15, 8], AtCoder::String.suffix_array([12, 8, 18, 18, 8, 18, 18, 8, 15, 15, 8])).should eq [1, 1, 4, 0, 0, 1, 0, 2, 1, 3] AtCoder::String.lcp_array([1, 2, 1, 2, 1, 3, 1, 3, 1], AtCoder::String.suffix_array([1, 2, 1, 2, 1, 3, 1, 3, 1])).should eq [1, 3, 1, 3, 0, 2, 0, 2] AtCoder::String.lcp_array([1, 1, 1, 1, 1], AtCoder::String.suffix_array([1, 1, 1, 1, 1])).should eq [1, 2, 3, 4] end end describe ".z_algorithm" do it "returns empty array if input sequence is empty" do AtCoder::String.z_algorithm([] of Int32).should eq [] of Int32 AtCoder::String.z_algorithm("").should eq [] of Int32 end it "returns the sequence of length n, such that the i-th element is the length of the LCP (Longest Common Prefix) of s[0...n] and s[i...n]." do AtCoder::String.z_algorithm("abcbcba").should eq [7, 0, 0, 0, 0, 0, 1] AtCoder::String.z_algorithm("mississippi").should eq [11, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] AtCoder::String.z_algorithm("ababacaca").should eq [9, 0, 3, 0, 1, 0, 1, 0, 1] AtCoder::String.z_algorithm("aaaaa").should eq [5, 4, 3, 2, 1] AtCoder::String.z_algorithm([1, 2, 3, 2, 3, 2, 1]).should eq [7, 0, 0, 0, 0, 0, 1] AtCoder::String.z_algorithm([1, 2, 3, 3, 2, 3, 3, 2, 4, 4, 2]).should eq [11, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] AtCoder::String.z_algorithm([1, 2, 1, 2, 1, 3, 1, 3, 1]).should eq [9, 0, 3, 0, 1, 0, 1, 0, 1] AtCoder::String.z_algorithm([1, 1, 1, 1, 1]).should eq [5, 4, 3, 2, 1] end end end