ให้ numo และ demo สองสตริงเป็นอินพุต เป้าหมายคือการหาจำนวนตัวหารร่วมของทั้งสองสตริง ตัวหารของสตริงถูกพบโดยใช้เทคนิคต่อไปนี้:หากสตริง str มี sub1 เป็นตัวหาร เราก็สามารถสร้าง str โดยใช้ sub1 ได้โดยการทำซ้ำหลายๆ ครั้งจนกว่า str จะถูกสร้างขึ้น ตัวอย่าง:str=abcabcbc sub1=abc
ตัวอย่าง
อินพุต
numo = "abababab" demo = "abababababababab"
ผลลัพธ์
Count of number of common divisors of the given strings are: 2
คำอธิบาย
The strings can be generated using following divisor substrings : “ab”, “abab”
อินพุต
numo = "pqqppqqp" demo = "pqpq"
ผลลัพธ์
Count of number of common divisors of the given strings are: 0
คำอธิบาย
The strings do not have any common divisor. Only divisors of both are: “pqqp” for numo and “pq” for demo.
แนวทางที่ใช้ในโปรแกรมด้านล่างมีดังนี้ −
สำหรับสตริงย่อย 1 ใดๆ ที่จะเป็นตัวหารของ str ต้องเป็นคำนำหน้าของ str และความยาวต้องหารความยาวของ str ทั้งหมด ตรวจสอบเงื่อนไขของ sub1 นี้ด้วยทั้งสตริง numo และ demo และนับจำนวนที่เพิ่มขึ้นตามลำดับ
-
รับสตริง numo และ demo เป็นอินพุต
-
ตรวจสอบฟังก์ชัน (สตริง str, int val) รับสตริง str และคืนค่า 1 หากสตริงย่อยระหว่าง 0 ถึง val สามารถทำซ้ำได้เพื่อสร้าง str
-
ฟังก์ชัน common_divisor(หมายเลขสตริง การสาธิตสตริง) รับทั้งสตริงและส่งคืนการนับจำนวนตัวหารร่วมของสตริงที่กำหนด
-
นับเริ่มต้นเป็น 0
-
คำนวณความยาวของสตริงอินพุต และเก็บความยาวขั้นต่ำเป็น min_val
-
สำรวจโดยใช้ for loop จาก index i=0 ถึง min_val.
-
หากความยาวปัจจุบัน i ของสตริงย่อยแบ่งความยาวของทั้งสองสตริง numo_size และdemo_size และคำนำหน้าก็ตรงกับ numo.substr(0, i) ==demo.substr(0, i)
-
จากนั้นค้นหาว่าสตริงย่อย 0 ถึง i เป็นตัวหารของทั้ง numo และ demo โดยใช้ Verify()
-
หากทั้ง Verify(numo,i) และ Verify(demo,i) คืนค่า 1 ให้นับจำนวนที่เพิ่มขึ้น
-
ที่ส่วนท้ายของ for loop จะคืนค่าเป็นผลลัพธ์
ตัวอย่าง
#include <bits/stdc++.h>
using namespace std;
int verify(string str, int val){
int length = str.length();
for (int i = 0; i < length; i++){
if(str[i] != str[i % val]){
return 0;
}
}
return 1;
}
int common_divisor(string numo, string demo){
int count = 0;
int numo_size = numo.size();
int demo_size = demo.size();
int min_val = min(numo_size, demo_size);
for(int i = 1; i <= min_val; i++){
if(numo_size % i == 0){
if(demo_size % i == 0){
if(numo.substr(0, i) == demo.substr(0, i)){
if(verify(numo, i)==1){
if(verify(demo, i)==1){
count++;
}
}
}
}
}
}
return count;
}
int main(){
string numo = "abababab";
string demo = "abababababababab";
cout<<"Count the number of common divisors of the given strings are:
"<<common_divisor(numo, demo);
return 0;
} ผลลัพธ์
หากเราเรียกใช้โค้ดข้างต้น มันจะสร้างผลลัพธ์ต่อไปนี้ -
Count the number of common divisors of the given strings are: 3
