Count the number of common divisors of the given strings | C ++ implementation of the approach ; Function that returns true if sub - string s [ 0. . . k ] is repeated a number of times to generate string s ; Function to return the count of common divisors ; If the length of the sub - string divides length of both the strings ; If prefixes match in both the strings ; If both the strings can be generated by repeating the current prefix ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int check ( string s , int k ) { for ( int i = 0 ; i < s . length ( ) ; i ++ ) if ( s [ i ] != s [ i % k ] ) return false ; return true ; } int countCommonDivisors ( string a , string b ) { int ct = 0 ; int n = a . size ( ) , m = b . size ( ) ; for ( int i = 1 ; i <= min ( n , m ) ; i ++ ) { if ( n % i == 0 && m % i == 0 ) if ( a . substr ( 0 , i ) == b . substr ( 0 , i ) ) if ( check ( a , i ) && check ( b , i ) ) ct ++ ; } return ct ; } int main ( ) { string a = " xaxa " , b = " xaxaxaxa " ; cout << countCommonDivisors ( a , b ) ; return 0 ; }