C++如何实现字符串的重复模式检测-C++-PHP中文网

重复模式指字符串能由某个非平凡子串（长度k整除总长n且k

c++如何实现字符串的重复模式检测

什么是重复模式？先看几个典型例子

字符串的重复模式检测，核心是判断一个字符串能否由某个子串重复拼接而成。比如 "abab" 可以拆成 "ab" 重复两次，"abcabcabc" 是 "abc" 重复三次，而 "abac" 就没有非平凡重复模式（排除单字符重复和自身作为“一次”这种退化情况）。

关键点在于：不是找最长重复子串，也不是找周期性子序列，而是验证是否存在长度为 k 的前缀 s[0:k]，使得整个字符串恰好等于该前缀重复 n/k 次（n 为总长，且 k 必须整除 n）。

最直接的做法：枚举所有可能的周期长度

对长度为 n 的字符串 s，只需检查所有满足 k 且 <code>n % k == 0 的 k 值：

枚举 k 从 1 到 n/2（因为最小重复单元至少出现两次）
若 n % k != 0，跳过
否则用 s.substr(0, k) 生成候选模式，再循环比对每段是否一致

bool hasRepeatingPattern(const std::string& s) {
    int n = s.size();
    if (n == 0) return false;
    for (int k = 1; k <p>这个做法简单、可读性强，时间复杂度最坏 <code>O(n²)</code>，但实际中多数短周期很快就能判定失败。</p><div class="aritcle_card flexRow artxards">
											<div class="artcardd flexRow">
												<a class="aritcle_card_img" rel="nofollow" href="/xiazai/skill4025" title="C++ 算法竞赛自动化测试数据生成与校验框架"><img
														src="https://img.php.cn/upload/skill/000/000/081/178988956499722.jpg" alt="C++ 算法竞赛自动化测试数据生成与校验框架" onerror="this.onerror='';this.src='/static/lhimages/moren/morentu.png'" ></a>
												<div class="aritcle_card_info flexColumn">
													<a rel="nofollow" href="/xiazai/skill4025" title="C++ 算法竞赛自动化测试数据生成与校验框架" class="overflowclass">C++ 算法竞赛自动化测试数据生成与校验框架</a>
													<p class="overflowclass">根据原题生成新题面、验证器及完整测试数据，自动套用 testlib 模板，用于用户要求生成测试数据时。</p>
												</div>
												<a rel="nofollow" href="/xiazai/skill4025" title="C++ 算法竞赛自动化测试数据生成与校验框架" class="aritcle_card_btn flexRow flexcenter"><b></b><span>下载</span>
												</a>
											</div>
										</div><h3>用 KMP 的 next 数组快速判断（避免 substring 开销）</h3><p>KMP 的 <code>next</code> 数组（或称 <code>lps</code>）能在线性时间内给出最长真前缀-后缀匹配长度。若字符串有重复模式，其最小周期为 <code>n - next[n-1]</code>，且必须满足：</p>

next[n-1] > 0
n % (n - next[n-1]) == 0

bool hasRepeatingPatternKMP(const std::string& s) {
    int n = s.size();
    if (n == 0) return false;
    std::vector<int> next(n, 0);
    for (int i = 1, j = 0; i  0 && s[i] != s[j]) j = next[j-1];
        if (s[i] == s[j]) ++j;
        next[i] = j;
    }
    int len = n - next[n-1];
    return next[n-1] > 0 && n % len == 0;
}
</int>

注意：这个方法只检测「最小完整重复单元」，不适用于像 "aaaa" 这种多级嵌套（它既是 "a" 重复 4 次，也是 "aa" 重复 2 次），但逻辑上只要存在任意一种非平凡重复即返回 true。