Discussion on String Function Calculation Challenge

4 months ago+ 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...
}