How can we solve substring matching check using Dynamic Programming

I learnt program to find longest common substring using dynamic programming. Can we also use dynamic programming to find out if substring exists in a string?

I tried it. However, it seem to be making things more complicated!

Below is the pseudo code of what I tried.

String : Helello

Substring : llo

f(n) : returns false if character of substring not found or the positions of found places

f(0) = matching indexes or false

f(1) = next index of f(0) index is substring[1] or false

f(2) = next index of f(1) index is substring[1] or false

f(n) = f(n-1) followed by next index of current char or false

Calling : substring('hello', 2, 'el' );

substring(str, n, substring)
{
        if(n == 0)
        {
                for(i=0;i<strlen(str);i++)
                {
                        if(str[i] == substring[n])
                                pos[] = i; //append i to positions array
                }
                if(pos) return pos;
                return false;
        }
        else
        {
                indexes = substring(str, n-1, substring);
                if(indexes)
                {
                        foreach(indexes as index)
                        {
                                if(str[index+1] == substring[n])
                                        return true;
                        }
                        return false;
                }
        }

}


ANSWERS:


I don't think you can solve that problem with DP.

For instance let's say you have a sentence S, and word W. You wanna to check if the given word W is a substring of sentence S. You can do that with DP only if the length of LCS(longest common substring) is equal to length of word W, which means that W is actually that LCS. Complexity is O(N * M) where N is length of S and M is length of W.

You can do much better with KMP, in O(N + M), or hashing.



 MORE:


 ? How can I implement the knapsack algorithm where the index of the array represent the weight of the item
 ? Dynamic Programming to Minimize Sum of Squares
 ? Why do naive solutions of dynamic programming problems take exponential time?
 ? Efficient Approach for Maximizing the number of Pairs
 ? dynamic programming to find the minimum weight cover of the points
 ? Robot coin collection - Dynamic Programming
 ? Using dynamic programming to find minimal sum in matrix
 ? Maximize the value of matrix after doing a specific matrix operation
 ? Unable to understand algorithm
 ? Executing a dynamic PL/SQL block to execute a sum and return a value