資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學能被兩個給定字串整除的最小字串
本文旨在確定最小的字串，它是兩個給定字串的倍數。一個有趣的觀察是，對於兩個給定的字串 s 和 t，字串 s 是 t 的倍數當且僅當 s 可以透過重複 t 一次或多次來形成。我們必須找到最小的這樣的字串。
問題陳述
給定兩個非空字串 s1 和 s2，長度分別為 n 和 m，目標是確定最小的字串，它是 s1 和 s2 的倍數。
如果存在一個字串 z 使得 x = yz，則字串 x 可被字串 y 整除。換句話說，y 是 x 的因子。能夠被 s 和 t 整除的字串必須是它們最大公約數 (GCD) 的倍數。
示例
Input: s1 = “abab”, s2 = “ab” Output: abab
解釋
s1 = s2 + s2。因此，最小的可整除字串是 s1 本身。
Input: s1 = “abcdef”, s2 = “z” Output: -1
解釋
s1 和 s2 的最大公約數不存在，因此不存在這樣的輸出。
Input: s1 = “aaaaa”, s2 = “aca” Output: -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”的最小公倍數 (LCM)。
連線字串“s”和“t”以形成一個新的字串“st”。
初始化一個名為“result”的空字串。
遍歷字串“s”和“t”，直到找到不匹配項。將匹配的字元新增到“result”字串。
如果兩個字串的長度相等，則輸出字串“s”並退出函式。
如果“s”的長度大於“t”，則交換“n”和“m”的值以及“s”和“t”的值。
在公共字首之後提取“t”的剩餘部分，並將其儲存在名為“repeatString”的字串中。
重複“repeatString” “l / m”次並將結果新增到“result”字串。
示例
以下是上述方法的程式：
#include <stdio.h>
#include <string.h>
// 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 compute the least common multiple of two numbers
int lcm(int num1, int num2) {
return (num1 / gcd(num1, num2)) * num2;
}
void findSmallestString(char *s, char *t) {
int n = strlen(s), m = strlen(t);
int l = lcm(n, m);
// Concatenate s and t to make st
char st[n + m + 1];
strcpy(st, s);
strcat(st, t);
// Initialize result string
char result[n + m + 1];
strcpy(result, "");
// Add the common prefix of s and t to the result string
for (int i = 0; i < (n < m ? n : m); i++) {
if (s[i] != t[i]) {
printf("-1\n");
return;
}
strncat(result, &s[i], 1);
}
// If s and t are equal, output s
if (n == m) {
printf("%s\n", s);
return;
}
// Swap s and t if n > m
if (n > m) {
int temp = n;
n = m;
m = temp;
char *tempStr = s;
s = t;
t = tempStr;
}
// Repeat the remainder of t (after the common prefix) (l / m) times
char repeatString[m - n + 1];
strcpy(repeatString, &t[n]);
for (int i = 0; i < l / m; i++) {
strcat(result, repeatString);
}
printf("%s\n", result);
}
int main() {
char S[] = "bcdbcd";
char T[] = "bcd";
printf("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
// 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
public class SmallestMultipleString {
// Function to determine the greatest common divisor of two numbers
static int gcd(int num1, int num2) {
if (num2 == 0)
return num1;
return gcd(num2, num1 % num2);
}
// Function to compute the least common multiple of two numbers
static int lcm(int num1, int num2) {
return (num1 / gcd(num1, num2)) * num2;
}
static void findSmallestString(String s, String t) {
int n = s.length();
int 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
StringBuilder result = new StringBuilder();
// Add the common prefix of s and t to the result string
for (int i = 0; i < Math.min(n, m); i++) {
if (s.charAt(i) != t.charAt(i)) {
System.out.println("-1");
return;
}
result.append(s.charAt(i));
}
// If s and t are equal, output s
if (n == m) {
System.out.println(s);
return;
}
// Swap s and t if n > m
if (n > m) {
int temp = n;
n = m;
m = temp;
String tempStr = s;
s = t;
t = tempStr;
}
// Repeat the remainder of t (after the common prefix) (l / m) times
String repeatString = t.substring(n);
for (int i = 0; i < l / m; i++) {
result.append(repeatString);
}
System.out.println(result);
}
public static void main(String[] args) {
String S = "bcdbcd";
String T = "bcd";
System.out.print("Minimum length string that is a multiple of the two given strings: ");
findSmallestString(S, T);
}
}
輸出
Minimum length string that is a multiple of the two given strings: bcdbcd
# Function to determine the greatest common divisor of two numbers
def gcd(num1, num2):
if num2 == 0:
return num1
return gcd(num2, num1 % num2)
# Function to compute the least common multiple of two numbers
def lcm(num1, num2):
return (num1 // gcd(num1, num2)) * num2
def find_smallest_string(s, t):
n = len(s)
m = len(t)
# Calculate LCM of n and m
l = lcm(n, m)
# Concatenate s and t to make st
st = s + t
# Initialize result string
result = ""
# Add the common prefix of s and t to the result string
for i in range(min(n, m)):
if s[i] != t[i]:
print("-1")
return
result += s[i]
# If s and t are equal, output s
if n == m:
print(s)
return
# Swap s and t if n > m
if n > m:
n, m = m, n
s, t = t, s
# Repeat the remainder of t (after the common prefix) (l // m) times
repeat_string = t[n:]
for i in range(l // m):
result += repeat_string
print(result)
S = "bcdbcd"
T = "bcd"
print("Minimum length string that is a multiple of the two given strings:", end=" ")
find_smallest_string(S, T)
輸出
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 個字元。此外，由 lcm 函式呼叫的 gcd 函式的時間複雜度也為 O(log n)。總的來說，程式的時間複雜度由 lcm 函式決定。
空間複雜度 - O(n)
程式的空間複雜度為 O(n)，其中 n 表示由 s 和 t 組合而成的連線字串的大小。這是因為程式儲存連線字串 st、結果字串和 repeatString 字串，所有這些字串的長度最多為 n 個字元。此外，gcd 和 lcm 函式需要恆定的空間，因此它們對整體空間複雜度的貢獻可以忽略不計。總的來說，程式的空間複雜度由字串儲存所需的空間決定。
結論
本文討論了一種樸素方法和一種高效方法，用於查詢長度最小的字串，該字串是兩個給定字串的倍數。透過詳細的示例解釋了問題的概念。解決方案方法附帶虛擬碼、各種程式以及時間和空間複雜度分析。
更新於：2023年10月27日
926 次瀏覽
廣告