Check if a string is concatenation of another given string
Given two strings str1 and str2 of length N and M respectively, the task is to check if the string str1 can be formed by concatenating the string str2 repetitively or not.
Examples:
Input: str1 = “abcabcabc”, str2 = “abc”
Output: Yes
Explanation:
Concatenating the string str2 thrice generates the string (“abc” + “abc” + “abc” = ) “abcabcabc”.
Therefore, the required output is Yes.Input: str1 = “abcabcab”, str2 = “abc”
Output: No
Approach: Follow the steps below to solve the problem:
- Traverse the strings str1 and str2.
- For each character of str1 and str2, check if str1[i] == str2[i % M] or not.
- If found to be false for any character, print “No”.
- Otherwise, print “Yes”.
Below is the implementation of the above approach:
C++
// C++ program to implement // the above approach #include <bits/stdc++.h> using namespace std; // Function to check if a string is // concatenation of another string bool checkConcat(string str1, string str2) { // Stores the length of str2 int N = str1.length(); // Stores the length of str1 int M = str2.length(); // If M is not multiple of N if (N % M != 0) { return false ; } // Traverse both the strings for ( int i = 0; i < N; i++) { // If str1 is not concatenation // of str2 if (str1[i] != str2[i % M]) { return false ; } } return true ; } // Driver Code int main() { string str1 = "abcabcabc" ; string str2 = "abc" ; if (checkConcat(str1, str2)) { cout << "Yes" ; } else { cout << "No" ; } } |
Java
// Java program to implement // the above approach import java.util.*; class GFG{ // Function to check if a String is // concatenation of another String static boolean checkConcat(String str1, String str2) { // Stores the length of str2 int N = str1.length(); // Stores the length of str1 int M = str2.length(); // If M is not multiple of N if (N % M != 0 ) { return false ; } // Traverse both the Strings for ( int i = 0 ; i < N; i++) { // If str1 is not concatenation // of str2 if (str1.charAt(i) != str2.charAt(i % M)) { return false ; } } return true ; } // Driver Code public static void main(String[] args) { String str1 = "abcabcabc" ; String str2 = "abc" ; if (checkConcat(str1, str2)) { System.out.print( "Yes" ); } else { System.out.print( "No" ); } } } // This code is contributed by Amit Katiyar |
Python3
# Python3 program to implement # the above approach # Function to check if a is # concatenation of another string def checkConcat(str1, str2): # Stores the length of str2 N = len (str1) # Stores the length of str1 M = len (str2) # If M is not multiple of N if (N % M ! = 0 ): return False # Traverse both the strings for i in range (N): # If str1 is not concatenation # of str2 if (str1[i] ! = str2[i % M]): return False return True # Driver Code if __name__ = = '__main__' : str1 = "abcabcabc" str2 = "abc" if (checkConcat(str1, str2)): print ( "Yes" ) else : print ( "No" ) # This code is contributed by mohit kumar 29 |
C#
// C# program to implement // the above approach using System; class GFG{ // Function to check if a String is // concatenation of another String static bool checkConcat(String str1, String str2) { // Stores the length // of str2 int N = str1.Length; // Stores the length // of str1 int M = str2.Length; // If M is not multiple // of N if (N % M != 0) { return false ; } // Traverse both the Strings for ( int i = 0; i < N; i++) { // If str1 is not // concatenation of str2 if (str1[i] != str2[i % M]) { return false ; } } return true ; } // Driver Code public static void Main(String[] args) { String str1 = "abcabcabc" ; String str2 = "abc" ; if (checkConcat(str1, str2)) { Console.Write( "Yes" ); } else { Console.Write( "No" ); } } } // This code is contributed by 29AjayKumar |
Javascript
<script> // javascript program for the // above approach // Function to check if a String is // concatenation of another String function checkConcat(str1, str2) { // Stores the length of str2 let N = str1.length; // Stores the length of str1 let M = str2.length; // If M is not multiple of N if (N % M != 0) { return false ; } // Traverse both the Strings for (let i = 0; i < N; i++) { // If str1 is not concatenation // of str2 if (str1[i] != str2[i % M]) { return false ; } } return true ; } // Driver Code let str1 = "abcabcabc" ; let str2 = "abc" ; if (checkConcat(str1, str2)) { document.write( "Yes" ); } else { document.write( "No" ); } </script> |
Output
Yes
Time Complexity: O(N)
Auxiliary Space: O(1)
Using a loop to check all possible concatenations in python:
Approach:
- Define a function named is_concatenation that takes two string arguments str1 and str2.
- Get the length of str2 and store it in the variable n.
- Use a for loop to iterate through the range from 0 to n-1.
- Inside the loop, create a string named concat which is equal to str2 multiplied by (n-i) times.
- Check if str1 is equal to concat concatenated with the first i characters of str2.
- If the condition is True, return True. Otherwise, continue the loop.
- If the loop completes without returning True, return False.
C++
#include <iostream> #include <string> bool isConcatenation(std::string str1, std::string str2) { int n = str2.length(); for ( int i = 0; i < n; i++) { // Create a string by repeating str2 to form a // potential concatenation std::string concat = str2; for ( int j = 1; j < (n - i); j++) { concat += str2; } // Check if str1 is equal to the concatenation of // concat and the beginning of str2 if (str1 == concat + str2.substr(0, i)) { return true ; } } return false ; } int main() { std::string str1 = "abcabcabc" ; std::string str2 = "abc" ; std::cout << std::boolalpha << isConcatenation(str1, str2) << std::endl; // Output: true str1 = "abcabcab" ; str2 = "abc" ; std::cout << std::boolalpha << isConcatenation(str1, str2) << std::endl; // Output: false return 0; } |
Java
public class ConcatenationCheck { public static boolean isConcatenation(String str1, String str2) { int n = str2.length(); for ( int i = 0 ; i < n; i++) { String concat = str2.repeat(n - i); if (str1.equals(concat + str2.substring( 0 , i))) { return true ; } } return false ; } public static void main(String[] args) { String str1 = "abcabcabc" ; String str2 = "abc" ; System.out.println(isConcatenation(str1, str2)); // Output: true str1 = "abcabcab" ; str2 = "abc" ; System.out.println(isConcatenation(str1, str2)); // Output: false } } |
Python3
def is_concatenation(str1, str2): n = len (str2) for i in range (n): concat = str2 * (n - i) if str1 = = concat + str2[:i]: return True return False # Testing the function str1 = "abcabcabc" str2 = "abc" print (is_concatenation(str1, str2)) # Output: True str1 = "abcabcab" str2 = "abc" print (is_concatenation(str1, str2)) # Output: False |
C#
using System; class Program { // Function to check if str1 is a concatenation of str2 static bool IsConcatenation( string str1, string str2) { int n = str2.Length; for ( int i = 0; i < n; i++) { // Create a string by repeating str2 to form a // potential concatenation string concat = str2; for ( int j = 1; j < n - i; j++) { concat += str2; } // Check if str1 is equal to the concatenation // of concat and the beginning of str2 if (str1 == concat + str2.Substring(0, i)) { return true ; } } return false ; } static void Main() { string str1 = "abcabcabc" ; string str2 = "abc" ; Console.WriteLine( IsConcatenation(str1, str2)); // Output: True str1 = "abcabcab" ; str2 = "abc" ; Console.WriteLine( IsConcatenation(str1, str2)); // Output: False } } |
Javascript
function is_concatenation(str1, str2) { const n = str2.length; for (let i = 0; i < n; i++) { const concat = str2.repeat(n - i); if (str1 === concat + str2.slice(0, i)) { return true ; } } return false ; } // Testing the function const str1 = "abcabcabc" ; const str2 = "abc" ; console.log(is_concatenation(str1, str2)); // Output: true const str1_2 = "abcabcab" ; const str2_2 = "abc" ; console.log(is_concatenation(str1_2, str2_2)); // Output: false |
Output
True False
Time Complexity: O(n^2)
Space Complexity: O(1)
Contact Us