We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
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.
usestd::error::Error;usestd::io::{BufReader,BufRead,stdin};fnmain()->Result<(),Box<dynError>>{lets=BufReader::new(stdin()).lines().map(|l|l.unwrap()).next().unwrap().chars().collect::<Vec<_>>();letlen=s.len();letsfx=suffix_array(&s);letmutlcp=lcp_array(&s,&sfx);letmutmax=len;forcenterin1..len{letmuti=center;letmutj=center;whilei>0&&lcp[i]>=lcp[center]{i-=1;}whilej<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.///fnsuffix_array(string:&[char])->Vec<usize>{// See link in post text above...}/// Create an LCP array using the Kasai algorithm.///fnlcp_array(string:&[char],suffixes:&[usize])->Vec<usize>{// See link in post text above...}
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
String Function Calculation
You are viewing a single comment's thread. Return to all 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 theO(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.