2022-08-28：把字符串 s 看作 “abcdefghijklmnopqrstuvwxyz“ 的无限环绕字符串

2022-08-28：把字符串 s 看作 “abcdefghijklmnopqrstuvwxyz” 的无限环绕字符串，
所以 s 看起来是这样的：
…zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd….
现在给定另一个字符串 p 。返回 s 中 不同 的 p 的 非空子串 的数量。
输入: p = “zab”。
输出: 6。

答案2022-08-28：

统计从以a结尾的最长字符的长度，从以b结尾的最长字符的长度，……，从以z结尾的最长字符的长度。最后全部累加就是需要的返回值。
时间复杂度：O(N)。

代码用rust编写。代码如下：

fn main() {
    let s = "zab";
    let ans = find_substring_in_wrapround_string(s);
    println!("ans = {}", ans);
}

fn find_substring_in_wrapround_string(s: &str) -> i32 {
    let str = s.as_bytes();
    let n = str.len() as i32;
    let mut ans = 0;
    let mut len = 1;
    // 256 0~255
    let mut max: [i32; 256] = [0; 256];
    max[str[0] as usize] += 1;
    for i in 1..n {
        let cur = str[i as usize];
        let pre = str[(i - 1) as usize];
        if (pre == 'z' as u8 && cur == 'a' as u8) || pre + 1 == cur {
            len += 1;
        } else {
            len = 1;
        }
        max[cur as usize] = get_max(max[cur as usize], len);
    }
    for i in 0..256 {
        ans += max[i as usize];
    }
    return ans;
}

fn get_max<T: Clone + Copy + std::cmp::PartialOrd>(a: T, b: T) -> T {
    if a > b {
        a
    } else {
        b
    }
}

执行结果如下：

左神java代码

本作品采用《CC 协议》，转载必须注明作者和本文链接