如何确定字符串的最小公约数? [英] How to determine the smallest common divisor of a string?

问题描述

我在求职面试中被问到以下问题，并被它难住了.

I was asked the following question during a job interview and was stumped by it.

我遇到的部分问题是对我要解决的问题下定决心.起初我不认为这个问题在内部是一致的，但后来我意识到它要求你解决两个不同的问题——第一个任务是弄清楚一个字符串是否包含另一个字符串的倍数.但是第二个任务是在两个字符串中找到一个更小的分割单位.

Part of the problem I had is making up my mind about what problem I was solving. At first I didn't think the question was internally consistent but then I realized it is asking you to solve two different things - the first task is to figure out whether one string contains a multiple of another string. But the second task is to find a smaller unit of division within both strings.

在我身后面试室的压力下，我现在更清楚了，但我仍然不确定这里的理想算法是什么.有什么建议吗?

It's a bit more clear to me now with the pressure of the interview room behind me but I'm still not sure what the ideal algorithm would be here. Any suggestions?

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.

Oddly, you're asked to return -1 unless s is divisible by t (which is easy to check), and then you're only left with cases where t divides s.

如果 t 除以 s，那么最小公约数就是 t 的最小约数.

If t divides s, then the smallest common divisor is just the smallest divisor of t.

找到 t 的最小除数的最简单方法是检查其长度的所有因子，看看该长度的前缀是否可以整除 t.

The simplest way to find the smallest divisor of t is to check all the factors of its length to see if the prefix of that length divides t.

您可以通过为 t 构建 Knuth-Morris-Pratt 搜索表来在线性时间内完成此操作:https://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm

You can do it in linear time by building the Knuth-Morris-Pratt search table for t: https://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm

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

This will tell you all the suffixes of t that are also prefixes of t. If the length of the remainder divides the length of t, then the remainder divides t.

这篇关于如何确定字符串的最小公约数?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！