我在面试时被问到以下问题，并被它难住了。
我遇到的部分问题是要下定决心要解决什么问题。起初我并不认为这个问题在内部是一致的，但后来我意识到它要求你解决两个不同的问题 - 第一个任务是弄清楚一个字符串是否包含另一个字符串的倍数。但第二个任务是在两个字符串中找到更小的除法单元。
现在，由于面试室的压力，我现在更加清楚了，但我仍然不确定这里的理想算法是什么。有什么建议么？
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.
奇怪的是，除非 s 能被 t 整除（这很容易检查），否则系统会要求您返回 -1，然后您就只剩下 t 整除 s 的情况。
如果 t 除 s，则最小公约数就是 t 的最小约数。
找到 t 的最小除数的最简单方法是检查其长度的所有因子，看看该长度的前缀是否能整除 t。
您可以通过为 t 构建 Knuth-Morris-Pratt 搜索表来在线性时间内完成此操作：https://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm https://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm
这将告诉您 t 的所有后缀也是 t 的前缀。如果余数的长度除以 t 的长度，则余数除以 t。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
