string - 将字符串表示为子字符串的某些幂

Question

给定一个字符串，我们必须检查该字符串是否可以由其重复有限次的子字符串表示。

ababab -> (ab)^3

我看到一个解决方案，它说首先找到最长的适当前缀，它也是一个后缀。让这个前缀的长度是一些 k。令 n 为原始字符串的长度。如果 n%(n-k) == 0，则字符串可以表示为重复有限次的子字符串。否则，不。

我无法理解此解决方案背后的逻辑。谁能解释一下为什么这个解决方案有效？我在哪里看到这个解决方案的链接:geeksforgeeks

Answer 1

好的，首先，让我们调用形成input的子串字符串 A .所以，

input = A ^ a (with a is constant)

我们可以看到，最长的既是后缀又是正确的前缀应该至少覆盖input的一半。如果input是一个电源字符串。证明很简单

• 如果 a是偶数，情况是微不足道的。

• 如果 a是奇数，所以 input = (A^b)A(A^b) ，我们可以看到，最长的前缀后缀至少应该是(A^b)A (with b = (a - 1)/2)

那么，现在让我们考虑三种情况:

• 如果长度k前缀后缀的是 k < n/2 , 所以 n - k > n/2 -> n % (n - k) != 0 ，如上所证，这个串不可能是幂串。

• 如果长度k前缀后缀的是 k = n/2 -> 这种情况很简单。

• 如果长度k前缀后缀的是 k > n/2 ，因此，我们可以将输入字符串可视化为

  input = ACA
  

  C是前缀和后缀的重叠区域，由于前缀和后缀相等，我们可以看出

  AC = CA 
  

  假设长度为 C > A , 为了 AC = CA , 所以 , 我们可以将 C 分为 C = A + B -> A + A + B = A + B + A , 这只有在 A == B 时才会发生.

  因此，输入的形式为 input = AAAA这显然是一根电源线。万一C = A , 我们有 input = AAA , 和案例 C < A可以证明类似于案例C > A .