LCP Array
(string/lcp-array/src/lib.rs)

• View this file on GitHub
• Last update: 2025-05-26 15:54:30+09:00
• Link: https://atcoder.github.io/ac-library/production/document_en/string.html

Description

Verified with

• verification/library-checker/number_of_substrings/src/main.rs

Code

//! https://atcoder.github.io/ac-library/production/document_en/string.html

#[derive(Debug)]
pub struct LCPArray;

impl LCPArray {
    pub fn lcp_array<T: Copy + Ord + PartialOrd>(s: &Vec<T>, sa: &Vec<usize>) -> Vec<usize> {
        assert!(s.len() == sa.len());
        let n = s.len();
        let mut rank = vec![0; n];
        for i in 0..n {
            assert!(sa[i] < n);
            rank[sa[i]] = i;
        }
        let mut lcp = vec![0; n - 1];
        let mut h = 0;
        for i in 0..n {
            if h > 0 {
                h -= 1;
            }
            if rank[i] == 0 {
                continue;
            }
            let j = sa[rank[i] - 1];
            while j + h < n && i + h < n {
                if s[j + h] != s[i + h] {
                    break;
                }
                h += 1;
            }
            lcp[rank[i] - 1] = h;
        }
        lcp
    }
}

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.11.12/x64/lib/python3.11/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.11.12/x64/lib/python3.11/site-packages/onlinejudge_verify/languages/rust.py", line 288, in bundle
    raise NotImplementedError
NotImplementedError

Back to top page