# String Function Calculation

# String Function Calculation

+ 1 comment I'm embarrassed to say that I don't even understand what the question is asking.

+ 2 comments This problem forced me to learn suffix tree. Implementation was special (hard) for Ukkonen's algorithm, solved in O(n) time complexity. Feel so good:D

+ 0 comments did it in python by constructing suffix array using SA-IS (https://zork.net/~st/jottings/sais.html) and the kasai to make the lcp

+ 0 comments Those who are struggling with suffix array construction and lcp_array construction, can refer here:

def maxValue(t): n = len(t) sa = suffix_array(t, n) lcp = lcp_array(t, sa, n) ans = n left, right = [-1]*n, [n]*n s = [0] for i in range(1,n): while s and lcp[s[-1]] >= lcp[i]: s.pop() if s: left[i] = s[-1] s.append(i) s = [n-1] for i in range(n-2, -1, -1): while s and lcp[s[-1]] >= lcp[i]: s.pop() if s: right[i] = s[-1] s.append(i) for i in range(n): ans = max(ans, lcp[i]*(right[i]-left[i])) return ans def suffix_array(s, n): sa, l = [[s[i],i] for i in range(n)], 0 while l < 2*n: sa.sort(key=lambda x: x[0]) last, rank, pos_map = sa[0][0], 0, [None]*n for i in range(n): pos_map[sa[i][1]] = i if last != sa[i][0]: last = sa[i][0] rank += 1 sa[i][0] = rank new_tuple = [(sa[i][0], sa[pos_map[sa[i][1]+l]][0] if sa[i][1]+l < n else -1) for i in range(n)] for i in range(n): sa[i][0] = new_tuple[i] l = 1 if not l else l << 1 return [i[1] for i in sa] def lcp_array(s, sa, n): rank, k, lcp = [None]*n, 0, [0]*n for i in range(n): rank[sa[i]] = i for i in range(n): if rank[i] == n-1: k = 0 continue j = sa[rank[i]+1] while i+k<n and j+k<n and s[i+k] == s[j+k]: k += 1 lcp[rank[i]] = k k = max(0, k-1) return lcp

+ 0 comments A solution in Rust. This was a good exercise to learn about suffix and LCP arrays. You can view the full code here (spoiler alert: contains full solution code). The simple approach to building the suffix array using a conventional sort algorithm won't be fast enough to beat the clock. Have to find something faster.

For a simple and sufficiently fast algorithm that constructs suffix arrays, and a good article explaining the code, this is a good reference. This algorithm is

`O(n log² n)`

, and is quite fast despite not being one of the`O(n)`

approaches.A good example for the Kasai LCP construction algorithm is here. This is the same algorithm I used.

There's a much better algorithm than the one below for finding the max string function value, but the one below is good enough to beat the timer on all test cases despite having terrible time-complexity (it's likely fast due to data locality). If you want an

`O(n)`

algorithm for this, search on "largest rectangle in histogram", or check the solution I linked.use std::error::Error; use std::io::{BufReader, BufRead, stdin}; fn main() -> Result<(), Box<dyn Error>> { let s = BufReader::new(stdin()).lines() .map(|l| l.unwrap()) .next().unwrap().chars() .collect::<Vec<_>>(); let len = s.len(); let sfx = suffix_array(&s); let mut lcp = lcp_array(&s, &sfx); let mut max = len; for center in 1..len { let mut i = center; let mut j = center; while i > 0 && lcp[i] >= lcp[center] { i -= 1; } while j < len && lcp[j] >= lcp[center] { j += 1; } max = max.max((j - i) * lcp[center]); } println!("{}", max); Ok(()) } /// Builds a suffix array. Much more time efficient than the /// substring sort method. /// fn suffix_array(string: &[char]) -> Vec<usize> { // See link in post text above... } /// Create an LCP array using the Kasai algorithm. /// fn lcp_array(string: &[char], suffixes: &[usize]) -> Vec<usize> { // See link in post text above... }

Sort 58 Discussions, By:

Please Login in order to post a comment