Distint Concat

Last Updated on June 10, 2020 by Harsh

Concepts Used

String

Difficulty Level

Hard

Problem Statement (Simplified):

Find the total number of substrings which are the concatenation of the same strings, e.g.PP if formed by concatenating P twice.

See original problem statement here

Test Case

Input:
1
xyzxyzxyz

Output:
3

Explanation:
Here we can see 'xyz' repeats twice at index 0 and 3 satisfying our requirements.

'yzx' repeats twice at index 1 and 4 satisfying our requirements.

'zxy' repeats twice at index 2 and 5 satisfying our requirements.

So, there are a total of 3 strings which makes a substring of form PP where P is required substring. So, 3 is the answer.

Solving Approach :

Bruteforce Approach:

1) In the naive approach, we can find all possible substrings of the given string and also notice their starting point. Then we check if give substring appears twice serial wise from the given index or not. If yes, we count the substring, else we move to the next substring.
2) This approach takes O(N^{2}) to find all substrings where N is the length of the given string. For each substring, it again takes O(2\times N) for matching its appearance. So, it totally takes O(N^{3}) time to process the whole string.
3) O(N^{3}) is very inefficient for string of size larger than 250. But our constraints give larger string than it, so we move to a more efficient approach.

Efficient Approach:

1) We can find the total number of such substrings if we can count substrings which start from every character of the string.
2) For every character, we check if substring from start to current character (Let’s say K) is the same as substring starting from current character to following characters of the same length as K.
3) If both strings are the same, we’have found one such required substring, thus we check if this substring has already been identified or not, if yes, we skip, else we count it as a unique substring.
4) We continuously check this for substrings starting from start to current character, and for all characters in the string.

Example and Video References

Disecho Solution (Youtube)

Solutions

#include<stdio.h>
#include<string.h>

int main(){

  int test;
  scanf("%d",&test);

  while(test--){

    char s[9999][99999];
    char a[99999];
    scanf("%s",a);

    int len = strlen(a);
    int count = 0;

    for(int i=1; i<len; i++){

      int start = 0, end = i;
      if(i<len/2){
        start = 0;
      }
      else{
        start = i+i-len;
      }

      while(start<end){

        int flag = 1;

        for(int j=start, k=end; j<end; j++, k++){
          if(a[j]!=a[k]){
            flag = 0;
            break;
          }
        }

        if(flag==1){

          char temp[20002];

          for(int k=0,j=start;j<end; j++,k++)
            temp[k] = a[j];
          temp[end-start] = '\0';

          flag = 0;

          for(int i=0; i<count; i++){
            if(strcmp(s[i],temp)==0){
              flag = 1;
              break;
            }
          }

          if(flag == 0)
            strcpy(s[count++],temp);

        }
        start++;
      }

    }

    printf("%d\n",count);

  }

}

#include<bits/stdc++.h>
using namespace std;

int main(){

  int test;
  cin>>test;

  while(test--){

    char s[9999][99999];
    char a[99999];
    cin>>a;

    int len = strlen(a);
    int count = 0;

    for(int i=1; i<len; i++){

      int start = 0, end = i;
      if(i<len/2){
        start = 0;
      }
      else{
        start = i+i-len;
      }

      while(start<end){

        int flag = 1;

        for(int j=start, k=end; j<end; j++, k++){
          if(a[j]!=a[k]){
            flag = 0;
            break;
          }
        }

        if(flag==1){

          char temp[20002];

          for(int k=0,j=start;j<end; j++,k++)
            temp[k] = a[j];
          temp[end-start] = '\0';

          flag = 0;

          for(int i=0; i<count; i++){
            if(strcmp(s[i],temp)==0){
              flag = 1;
              break;
            }
          }

          if(flag == 0)
            strcpy(s[count++],temp);

        }
        start++;
      }

    }

    cout<<count<<endl;

  }

}

for _ in range(int(input())):

	s = [[] for x in range(9999)]
	a = input()
	l = len(a)

	count = 0

	for i in range(1, l):
		
		start = 0
		end = i

		if(i<l/2):
			start = 0
		
		else:
			start = i+i-l
		

		while(start < end):

			flag = 1
			k = end
			
			for j in range(start, end):
				
				if a[j] != a[k]:
					flag = 0
					break
				
				k += 1

			if(flag==1):

				temp = [""] * 20002
				k = 0
				
				for j in range(start, end):
					
					temp[k] = a[j]
					temp[end-start] = '\0'
					flag = 0
					k += 1

				for i in range(count):

					if(s[i] == temp):
						flag = 1
						break

				if(flag == 0):
					s[count] = temp
					count += 1
			
			start += 1
			
	print(count)

[forminator_quiz id=”1194″]

Space Complexity of this approach would be O(N).