두 개의 문자열 numo 및 demo가 입력으로 제공됩니다. 목표는 두 문자열의 공약수의 수를 찾는 것입니다. 문자열의 제수는 다음 기술을 사용하여 찾을 수 있습니다. 문자열 str에 제수로 sub1이 있는 경우 str이 생성될 때까지 여러 번 반복하여 sub1을 사용하여 str을 구성할 수 있습니다. 예:str=abcabcabc 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.
아래 프로그램에서 사용된 접근 방식은 다음과 같습니다. -
문자열 sub1이 str의 제수가 되려면 str의 접두어여야 하고 그 길이는 str의 길이를 완전히 나누어야 합니다. numo 및 demo 문자열을 사용하여 sub1의 이 조건을 확인하고 그에 따라 카운트를 증가시키십시오.
-
문자열 numo 및 demo를 입력으로 사용합니다.
-
함수 verify(string str, int val)은 문자열 str을 사용하고 0에서 val 사이의 하위 문자열을 반복하여 str을 생성할 수 있는 경우 1을 반환합니다.
-
함수 common_divisor(string numo, string demo)는 두 문자열을 모두 취하고 주어진 문자열의 공약수 개수를 반환합니다.
-
초기 카운트를 0으로 합니다.
-
입력 문자열의 길이를 계산합니다. 그리고 min_val에 최소 길이를 저장합니다.
-
for 루프를 사용하여 인덱스 i=0에서 min_val까지 순회합니다.
-
부분 문자열의 현재 길이 i가 두 문자열 numo_size 및demo_size의 길이를 나누고 접두사도 numo.substr(0, i) ==demo.substr(0, i)와 일치하는 경우
-
그런 다음 verify()를 사용하여 부분 문자열 0에서 i까지가 numo와 demo의 제수인지 확인합니다.
-
verify(numo,i)와 verify(demo,i)가 모두 1을 반환하면 count를 증가시킵니다.
-
for 루프가 끝나면 count를 결과로 반환합니다.
예시
#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