459. 重复的子字符串

题目描述

给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。

解题思路

例子

abcabcabcabc
000123456789

abaaba
001123

abacabacabac
001012345678

abac
0010

abcabc
000123

#![allow(unused)]

fn main() {
struct Solution {}

impl Solution {
    pub fn repeated_substring_pattern(s: String) -> bool {
        let n = s.len();
        let mut next = vec![0; n];
        let s = s.chars().collect::<Vec<char>>();
        let mut j = 0;
        for i in 1..n {
            while j >= 1 && s[i] != s[j] {
                j = next[j - 1];
            }
            if s[i] == s[j] {
                j += 1;
            }
            next[i] = j;    // next 表示以i结尾的字符串最大前后缀长度
        }
        let a = *next.last().unwrap();
        if a == 0 { return false }
        let b = n - a;
        if n % b != 0 { return false }
        else { true }
    }
}

}

学习感想

什么时候该用KMP很懵

next 数组 -- 前缀表 内容是什么？？next[i] 记录下标i之前（包括i）的字符串中，有多大长度的相同前缀后缀

前缀表是用来回退的，它记录了模式串P与主串(文本串)不匹配的时候，模式串应该从哪里开始重新匹配。

记录下标i之前（包括i）的字符串中，有多大长度的相同前缀后缀。

记住例子

abcdabcd
00001234

#![allow(unused)]
fn main() {
struct Solution {}

impl Solution {
    pub fn repeated_substring_pattern(s: String) -> bool {
        let s: Vec<u8> = s.bytes().collect();
        // next[i] -> max length of common prefix & suffix of string s[0..=i]
        let mut next: Vec<usize> = vec![0usize; s.len()];
        let mut left: usize = 0usize;   // the current max length of common pre/suf-fix
        for right in 1usize .. next.len() { // calculate each next[right]
            while left > 1usize && s[right] != s[left] {
                left = next[left - 1usize];
            }
            if s[right] == s[left] {
                left += 1usize;
            }
            next[right] = left;
        }
        let x: usize = s.len() - *next.last().unwrap();
        match s.len() % x {
            0 => true,
            _ => false,
        }
    }
}
}