C++ 两个给定字符串的最小公倍数

这篇文章的目标是确定一个既是给定两个字符串的倍数又是最小字符串的字符串。一个有趣的观察是，对于给定的两个字符串s和t，只有当s可以由t重复一次或多次形成时，字符串s才是t的倍数。我们需要找到最小的这样的字符串。

问题陈述

给定两个非空字符串s1和s2，长度分别为n和m，目标是确定一个既是s1和s2的倍数又是最小字符串的字符串。

如果存在一个字符串z使得x=yz，则字符串x可被字符串y整除。换句话说，y是x的因子。既能被s和t整除的字符串必须是它们最大公约数的倍数。

示例

输入

s1 = “abab”, s2 = “ab”

输出

abab

解释

s1 = s2 + s2。因此，最小的可被整除的字符串是s1本身。

输入

s1 = “abcdef”, s2 = “z”

输出

-1

解释

s1和s2的最大公约数不存在，因此不存在这样的输出。

输入

s1 = “aaaaa”, s2 = “aca”

输出

-1

解释

s1和s2的最大公约数不存在，因此不存在这样的输出。

解决方法

用于找到长度最短且是字符串S和T的倍数的字符串的蛮力方法是生成两个字符串的所有可能组合，并检查每个组合是否同时被S和T整除。我们可以先生成S和T的所有可能子字符串，然后将它们连接起来形成所有可能的组合。

生成所有可能的组合后，我们可以检查每个组合是否被S和T整除。为了确定一个字符串是否被另一个字符串整除，可以使用取模运算符来检查在将字符串除以另一个字符串时余数是否为零。

这种蛮力方法的时间复杂度是O(N^3)，其中N表示输入字符串的长度。对于大型输入大小，这种方法效率低下，因此我们使用基于最大公约数（GCD）概念的更高效的方法。

步骤

声明并初始化一个名为”findSmallestString”的函数，该函数以参数形式接受字符串”s”和”t”作为输入。
使用字符串”s”和”t”的长度初始化两个整数”n”和”m”
使用”lcm”函数计算”n”和”m”的最小公倍数
将字符串”s”和”t”连接起来形成一个新的字符串”st”
初始化一个名为”result”的空字符串
遍历字符串”s”和”t”，直到找到不匹配的字符。将匹配的字符附加到”result”字符串中。
如果两个字符串的长度相等，则输出字符串”s”并退出函数
如果”s”的长度大于”t”，则交换”n”和”m”的值以及”s”和”t”的值
提取”t”中公共前缀后的剩余部分，并将其存储在名为”repeatString”的字符串中
将”repeatString”重复”l / m”次，并将结果附加到”result”字符串中

示例：C++程序

该程序定义了一个名为findSmallestString()的函数，该函数接受两个字符串s和t作为输入，并找到能够同时被s和t整除的最小字符串。该函数首先计算s和t的长度的最小公倍数LCM，然后将s和t拼接成一个新的字符串st，并通过迭代它们的字符来找到s和t的共同前缀。如果共同前缀不相同，则函数返回-1，表示没有能够同时被s和t整除的共同字符串。如果s和t的长度相同，则函数返回s。否则，如果n > m（其中n和m分别是s和t的长度），则函数交换s和t。最后，函数将公共前缀之后的t的剩余部分（重复l / m次）添加到结果字符串中，并将结果字符串输出。主函数使用两个示例输入字符串调用findSmallestString函数并打印输出。

示例

// C++ program to find the minimum length string that is a multiple of the two given strings
#include <iostream>
#include <string>
using namespace std;

// Function to determine the greatest common divisor of two numbers
int gcd(int num1, int num2) {
   if (num2 == 0)
   return num1;
   return gcd(num2, num1 % num2);
}
// Function to computer the least common multiple of two numbers
int lcm(int num1, int num2) {
   return (num1 / gcd(num1, num2)) * num2;
}
// Function to find the string of minimum length which is a multiple of strings s and t
void findSmallestString(string s, string t) {
   int n = s.length(), m = t.length();
   // Calculate LCM of n and m
   int l = lcm(n, m);
   // Concatenate s and t to make st
   string st = s + t;
   // Initialize result string
   string result = "";
   // Add the common prefix of s and t to the result string
   for (int i = 0; i < min(n, m); i++) {
      if (s[i] != t[i]) {
         cout << -1 << endl;
         return;
      }
      result += s[i];
   }
   // If s and t are equal, output s
   if (n == m) {
      cout << s << endl;
      return;
   }
   // Swap s and t if n > m
   if (n > m) {
      swap(n, m);
      swap(s, t);
   }
   // Repeat the remainder of t (after the common prefix) (l / m) times
   string repeatString = t.substr(n);
   for (int i = 0; i < l / m; i++) {
      result += repeatString;
   }
   // Print the resultant string
   cout << result << endl;
}
int main() {
   string S = "bcdbcd", T = "bcd";
   cout << "Minimum length string that is a multiple of the two given strings: "; 
   findSmallestString(S, T);
   return 0;
}

输出

Minimum length string that is a multiple of the two given strings: bcdbcd

时间复杂度：O(n*log n)

程序的时间复杂度由lcm函数确定，该函数的时间复杂度为O(log n)，其中n是由s和t形成的连接字符串的长度。然后程序迭代结果字符串的长度，结果字符串的长度最长可以是n + m。此外，gcd函数，被lcm函数调用，其时间复杂度也为O(log n)。总的来说，程序的时间复杂度由lcm函数主导。

空间复杂度：O(n)

程序的空间复杂度为O(n)，其中n表示由s和t组合而成的连接字符串的大小。这是因为程序存储了连接字符串st，结果字符串和repeatString字符串，它们都可以最长为n个字符。此外，gcd和lcm函数需要一个常量大小的空间，所以它们对整体空间复杂度的贡献是可以忽略不计的。总的来说，程序的空间复杂度由字符串所需的存储空间主导。