string - 如何确定字符串的最小公约数？

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.

Answer 1

奇怪的是，除非 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

这将告诉您 t 的所有后缀，同时也是 t 的前缀。如果余数的长度除以 t 的长度，则余数除以 t。