2023-05-17 • 于匹配模式, 字符串, 算法阅读

字符串最短循环子串

问题

问题描述

小M在研究字符串时发现了一个有趣的现象：某些字符串是由一个较短的子串反复拼接而成的。如果能够找到这个最短的子串，便可以很好地还原字符串的结构。你的任务是给定一个字符串，判断它是否是由某个子串反复拼接而成的。如果是，输出该最短的子串；否则，输出空字符串""。

例如：当输入字符串为 abababab 时，它可以由子串 ab 反复拼接而成，因此输出 ab；而如果输入 ab，则该字符串不能通过子串的重复拼接得到，因此输出空字符串。

测试样例

样例1：

输入：inp = "abcabcabcabc" 输出：'abc'

样例2：

输入：inp = "aaa" 输出：'a'

样例3：

输入：inp = "abababab" 输出：'ab'

样例4：

输入：inp = "ab" 输出：''

样例5：

输入：inp = "abcdabcdabcdabcd" 输出：'abcd'

样例6：

输入：inp = "b" 输出：''

分析

思路说明

题目要求判断一个字符串是否可以由某个子串反复拼接而成，并输出该最短的子串。核心信息是字符串的周期性。我们可以通过遍历字符串的长度，找到所有可能的子串长度，并验证这些子串是否能重复拼接成原字符串。如果找到这样的子串，则输出该子串；否则，输出空字符串。

解题过程

遍历可能的子串长度：
1. 从长度为1到n-1的子串中，找到所有可能的子串长度。
2. 对于每个子串长度i，判断n是否能被i整除（即$$n % i == 0$$）。
验证子串的重复性：
1. 如果n能被i整除，则取出前i个字符作为子串t。
2. 计算子串t重复$$n / i$$（表示n除以i的整数部分）次后是否等于原字符串。
3. 如果相等，则返回子串t。
返回结果：
1. 如果遍历完所有可能的子串长度都没有找到符合条件的子串，则返回空字符串。

复杂度分析

时间复杂度：
- 遍历可能的子串长度需要$$O(n)$$次操作。
- 对于每个可能的子串长度，验证子串的重复性需要$$O(n)$$次操作。
- 因此，总的时间复杂度为$$O(n^2)$$。
空间复杂度：
- 仅使用了常数级别的额外空间，因此空间复杂度为$$O(1)$$。

知识点扩展

字符串处理：
- 字符串的切片操作和拼接操作。
- 字符串的周期性判断。
数学分析：
- 整除运算和倍数关系。
- 通过数学分析减少不必要的计算。

解答

fn solution(inp: &str) -> String {
    // 记录原字符串长度
    let n = inp.len();
    
    // 遍历从 1 到 n-1 的整数范围，这里取的是子串可能的长度
    // 这个循环的目的是检查从 1 到 n-1 的每一个长度 i，
    // 看看是否存在一个子串 t，使得 t 重复若干次后可以构成原字符串 inp。
    for i in 1..n {
        // 检查子串长度是否能被原字符串长度整除，不能被整除则说明无法构成原字符串
        if n % i == 0 {
            // 截取可能的子串
            let t = &inp[0..i];
            // 检查子串重复 n/i 次后是否等于原字符串
            if t.repeat(n / i) == inp {
                return t.to_string();
            }
        }
    }
    
    // 如果没找到模式，返回空字符串
    String::new()
}

fn main() {
    println!("{}", solution("abcabcabcabc") == "abc");
    println!("{}", solution("aaa") == "a");
    println!("{}", solution("abababab") == "ab");
    println!("{}", solution("ab") == "");
    println!("{}", solution("abcdabcdabcdabcd") == "abcd");
    println!("{}", solution("b") == "");
}

这道题中用到的算法技巧可以归类为字符串处理和模式匹配。具体来说，它涉及到以下几个方面：

字符串分割与比较：通过遍历字符串的不同子串长度，并检查这些子串是否可以重复构成原字符串。
整除性检查：通过检查字符串长度是否能被某个子串长度整除，来判断该子串是否可能构成原字符串。
子串重复性验证：通过逐段比较字符串的不同部分，验证是否由某个子串重复构成。

这些技巧在字符串处理和模式匹配问题中非常常见，尤其是在需要识别重复模式或周期性结构的字符串问题中。

跃迁引擎