没有搜索表的字符串可除性？

Question

Given two strings s & t, determine if s is divisible by t. For example: "abab" is divisible by "ab" But "ababab" is not divisible by "abab". If it isn't divisible, return -1. If it is, return the length of the smallest common divisor: So, for "abababab" and "abab", return 2 as s is divisible by t and the smallest common divisor is "ab" with length 2.

我思考的方式是：我定义这两个字符串的长度，找到这两个字符串的最大公约数。如果t除以s，那么最小的公约数就是t的最小除数。然后我们可以使用这个算法：https://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm

有没有更简单的解决办法

Answer 1

要测试可分性：

1. 测试s的长度是t长度的倍数（否则不可分割）
2. 将s分成长度为t的块；及
3. 检查所有块是否相同

要找到最小公约数，需要找到构成整个t的t的最短重复子串。一种方法是：

1. 找出t长度的因素（对于任何合理长度的管柱，从1到sqrt（len（t））的粗略搜索方法应适用）

2. 对于每个系数（从最小值开始）：

   一,。将t划分为长度因子块

   二,。检查所有区块是否相同，如果相同，则返回因子

使用Python集是检查列表中所有块是否相等的一种好方法。len（set（chunks））==1表示它们是

Answer 2

字符串长度的GCD对您没有帮助

如果len(s)是len(t)和s == t * (len(s)//len(t))的倍数，则字符串t将字符串s除以

至于求t最小除数的长度，经典的技巧是(t+t).index(t, 1)：在t+t中求t的第一个非零索引。我在这里使用了内置的index方法，但是根据执行此操作的原因以及所需的运行时属性，KMP字符串搜索可能是更好的选择。在Python中手动实现KMP将有巨大的常数因子开销，但它在最坏情况下的运行时将比index好得多

就字符串搜索而言，KMP实现起来并不特别困难。如果不将任务委托给库例程或牺牲渐进复杂性属性（或两者兼而有之），您将不会得到任何明显“更简单”的结果

如果您想要避免搜索表并保持渐进复杂性保证，可以使用类似two-way string matching的东西，但它不会比KMP更容易实现