#NOTE: Below i have consistently used the word "occurrences"..
By occurrences i mean the no. of ways Str2 can be formed
by using chars of Str1...
Algo:
----------
An O(K*N) approach with O(K*N) space..
Here,
N = size of the first string..
K = size of the 2nd string... (search string)..
Let the string be denoted by Str1[N] and Str2[K]...
Say, P(N, K) denotes the no. of occurrences of Str2[K] in Str1[N]..
If we observe the end chars of both the strings then the following
recurrence will follow:
P(N, K) =
P(N-1, K-1) , if Str1[N] == Str2[K]
+
P(N-1, K) // irrespective of whether the end chars match get the no.
of occurrences of the K chars in N-1 chars...
Code:
----------
Lets take an array X[K+1][N+1] to keep track of P(N,K)...
here the 0th row and 0th column represents empty string and therefore
we will initialize the 0th row and column as follows.
// Occurrence of empty string in substrings of Str1...
for (int i = 0; i <= N; ++i)
X[0][i] = 1;
// Occurrence of Str2 substrings in empty string....
for (int i = 1; i <=K; ++i)
X[i][0] = 0;
// In the code below, the chars in Str1 and Str2 have been accessed
based on 1-based indexing so that the index directly maps to indices
in array X....
for (int i = 1; i <=K; ++i)
for ( int j = 1; j<=N; ++j)
X[i][j] = ( Str1[i] == Str1[j] ? X[i-1][j-1] : 0 ) + X[i][j-1];
The max no. of occurrences will be given by X[K][N]....
On Dec 29, 12:47 am, Tamanna Afroze <[email protected]> wrote:
> This is really an interesting problem. If it is searched from the left to
> right the most possible subset is 7 and for the 8th number we have to track
> from right to left.
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
