Đếm số ước chung của các chuỗi đã cho trong C ++

Cho hai chuỗi numo và demo làm đầu vào. Mục đích là để tìm số ước chung của cả hai chuỗi. Các ước của một chuỗi được tìm thấy bằng cách sử dụng kỹ thuật sau:Nếu chuỗi str có sub1 là ước của nó thì chúng ta có thể xây dựng str bằng cách sử dụng sub1 bằng cách lặp lại nó bất kỳ số lần nào cho đến khi str được tạo. Ví dụ:str =abcabcabc sub1 =abc

Ví dụ

Đầu vào

numo = "abababab" demo = "abababababababab"

Đầu ra

Count of number of common divisors of the given strings are: 2

Giải thích

The strings can be generated using following divisor substrings :
“ab”, “abab”

Đầu vào

numo = "pqqppqqp" demo = "pqpq"

Đầu ra

Count of number of common divisors of the given strings are: 0

Giải thích

The strings do not have any common divisor. Only divisors of both are:
“pqqp” for numo and “pq” for demo.

Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau -

Đối với bất kỳ chuỗi con1 nào là ước của str, nó phải là tiền tố của str và độ dài của nó phải chia hết độ dài của str. Kiểm tra điều kiện này của sub1 với cả numo chuỗi và demo và số lượng gia tăng tương ứng.

• Lấy numo chuỗi và demo làm đầu vào.

• Hàm verify (string str, int val) nhận chuỗi str và trả về 1 nếu chuỗi con giữa 0 đến val có thể được lặp lại để tạo str.

• Hàm common_divisor (string numo, string demo) nhận cả hai chuỗi và trả về số lượng ước chung của các chuỗi đã cho.

• Lấy số lượng ban đầu là 0.

• Tính độ dài của chuỗi đầu vào. Và lưu trữ độ dài tối thiểu theo min_val.

• Di chuyển bằng vòng lặp for từ chỉ mục i =0 đến min_val.

• Nếu độ dài hiện tại i của chuỗi con chia độ dài của cả chuỗi numo_size vàdemo_size và các tiền tố cũng khớp với numo.substr (0, i) ==demo.substr (0, i).

• Sau đó, tìm xem chuỗi con từ 0 đến i có phải là ước của cả numo và demo hay không bằng cách sử dụng verify ()

• Nếu cả xác minh (numo, i) và xác minh (demo, i) trả về 1 thì số gia tăng.

• Ở cuối vòng lặp for, kết quả trả về là số lượng.

Ví dụ

#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;
}

Đầu ra

Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra kết quả sau -

Count the number of common divisors of the given strings are: 3