count the number of occurences of a string in another string

[tomjackson]

This could be non contiguous. As an example
string1: "Hello"
string2: "Heelblloo"
occurences of string 1 in string2 is 2*3c2*2=12
among 2 e's in string 2, we can select only one and thus 2 possible ways.similarly for l and o. I am trying hard to implement it in the C programming,but getting messed up using dynamic programming to find the proper logic. suggestions please

[weaknessforcats]

rite a loop that arches down your target string a character at a time.

Next, modify the loop s it terminates when it reaches strlen(searchstring).


Next, inside the loop call strstr using your current position in the target string and your search string.

Use the return from strstr to see if you have an occurrence.

[tomjackson]

thanks for your response.I doubt that strstr function only compares the string as it is in the target string where as here in the example, the characters in the string need not be contiguous.I am new to strstr function and never used it. If my claim is wrong, please elaborate your suggestion with the code.

[weaknessforcats]

OK. Before I go on with more logic, I need to be sure of the problem conditions. What does:

string1: "Hello"
 string2: "Heelblloo"
 occurences of string 1 in string2 is 2*3c2*2=12

mean? I see only one occurrence of Hello because there is only one H in string1.

[tomjackson]

I will correct my title to "number of ways to form string1 from string2"
1) H can be found in 1st location of string2.Hence that should form as a part of the solution.
2) 'e' of string1 can be formed by selecting either of 'e' in 2nd and 3rd position from string2. thus 2 possible ways.
3) Thus we formed "He". "ll" can be formed by selecting "ll" from (4,6),(4,7) and (6,7) Thus 3c2 ways as we need two l's from 3. we can safely ignore 'b' as it does not form the solution.
4) similarly one 'o' can be selected from two 'o's at the final and last but one position..
5) Multiplying all will give final answer.

Note: The string2 should be scanned sequentially.
suggest me the best way to implement it.

[weaknessforcats]

The easiest thing is to extract all the letters from string2 that occur in string1.

You would then need to find all combinations of these letters taken n at a time where n is the number of letters in string1.

After each combination you would compare the combination to the string1.

Eventually all matching combinations would appear.

[tomjackson]

I tried the approach, and it is giving the correct answer,until the character is repeating in the adjacent locations with O(n) complexity. But the code is failing if the string2 has repeated characters with some intermediate new characters like "hellbblaobllboo".

while(str2[k]!='\0' || str1[j]!='\0' )
            {
                if(str1[j]==str2[k])
                {
                    count2[j]+=1;
                    if(str2[k]!='\0')
                        k++;
                }
                else if (j==8) break;// end of string
                else j++;
 
            }
for(j=0;j<8;j++)
                product=product*combination(count2[j],count1[j]);
int combination(int n,int r)
{
    return fact(n)/(fact(n-r)*fact(r));
}

How to fix this bug or could it done by dynamic programming?

[weaknessforcats]

I was thinking more along the lines of:

if (!strcmp(string1,combo))
{
    increment match count
}