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 stringbool 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 Codeint main(){ string str1 = "abcabcabc"; string str2 = "abc"; if (checkConcat(str1, str2)) { cout << "Yes"; } else { cout << "No"; }} |
Java
// Java program to implement// the above approachimport java.util.*;class GFG{// Function to check if a String is// concatenation of another Stringstatic 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 Codepublic 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 stringdef 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 Codeif __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 approachusing System;class GFG{// Function to check if a String is// concatenation of another Stringstatic 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 Codepublic 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 Stringfunction 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 functionstr1 = "abcabcabc"str2 = "abc"print(is_concatenation(str1, str2)) # Output: Truestr1 = "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 functionconst str1 = "abcabcabc";const str2 = "abc";console.log(is_concatenation(str1, str2)); // Output: trueconst 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)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
… [Trackback]
[…] Here you can find 45592 more Info to that Topic: geeksforgeeks.org/check-if-a-string-is-concatenation-of-another-given-string/ […]
… [Trackback]
[…] Read More on on that Topic: geeksforgeeks.org/check-if-a-string-is-concatenation-of-another-given-string/ […]