Question: A binary string is given with only 0's and 1's. A number n is also given as the length of a sub string to be considered. It is to find the number of unique substrings. Here, n=3.
My algorithm: The ways I followed: (i) First, I extracted out the sub string of length 3 and converted it into a number. (ii) Then, I stored the number in a new integer type array. In this way, I had an integer array full of numbers representing the substrings. (iii) Lastly, I traversed down the array, keeping track of the occurrence of the unique numbers only. The amount of unique numbers therefore correspond to the number of unique substring.
#include<stdio.h>
#include <string.h>
int main(void)
{
char arr[50];
int o[50],check[10000];
int i,j,count=1,l,k=0,sum,p;
l=strlen(arr);
for(i=0;i<l-2;i++){
p=4;sum=0;
for(j=0;j<3;j++){
sum+=(arr[i+j]-'0')*p;
p/=2;
}
o[k++]=sum;
}
memset(check,0,sizeof(check));
for(i=0;i<k-1;i++){
for(j=i+1;j<k;j++){
if(o[i]!=o[j] && check[o[i]]!=1 && check[o[j]]!=1){
count++;
check[o[j]]=1;
}
}
check[o[i]]=1;
}
printf("\n%d",count);
return 0;
}
I think that my code is quite long and it could be shortened with a good optimization. But I can't think of a way.