侧边栏壁纸
  • 累计撰写 43 篇文章
  • 累计创建 0 个标签
  • 累计收到 32 条评论

目 录CONTENT

文章目录

求字符串前缀最长的连续重复子串(不重叠)

问题描述

1 2 3 4 5 6 7 8 9 10 11 12 13
a b a b a b a b f c e b d

字符串 ababababfcebd 的长度为 n = 13,现在要求字符串从开始位置1开始最长的连续重复子串(没有重叠。即 ababacb 预期的结果是 ab,而不是 aba。)

boolean flag = false;	// 标记是否存在这样的子串
for (int i = n / 2; i >= 1; i--) {
  boolean b = 比较 [1, i] 和 [i + 1, 2 * i] 连续子串是否相等;	// 相等 b 为 true
  if (b == true && flag == false) {
    flag = true;	// 存在
    其它操作
  }
}

if (flag == false)	// 不存在
  其它操作

上边的例子:

i flag
6 [1, 6] [7, 12] false
5 [1, 5] [6, 10] false
4 [1, 4] [5, 8] true
3 [1, 3] [4, 6] true
2 [1, 2] [3, 4] true
1 [1, 1] [1, 1] true

伪代码中的语句 if (b == true && flag == false) 不可以写成 if (b == true) ,因为若写成后者,无法保证是最长的连续重复子串了。

Reference

0

评论区