Number of unique substrings of particular length of a binary string

Question

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.

Answer 1

Your code can be more efficient. For example, both nested for-loops can be replaced with single for-loops. In the first loop, the next sum can be calculated by left-shifting the previous sum, adding the new bit, and masking off n-bits. count[sum] is how many times an n-bit pattern == sum has been seen. So the second loop merely counts how many '1's are in count. Something like the code below (not tested).

int count_unique(char *arr, int n) {
    int mask = (1 << n) - 1;

    /* the size needs to be 2**n.  This works for n <= 10 */
    int count[1024];
    memset(count, 0, sizeof(count));

    int sum = 0;

    for (int i = 0; arr[i]; i++) {
        sum = ((sum << 1) | (arr[i] - '0')) & mask;

        if (i >= n - 1) {
            count[sum]++;
        }
    }

    int unique = 0;

    for (int i = 0; i < sizeof(count)/sizeof(int); i++) {
        if (count[i] == 1) {
           unique++;
        }
    }

    return unique;
}