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

问题描述

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

• 字符串哈希