You are given a string and a pattern. You find the pattern on the given string. If found print how many times found the pattern and their index. Otherwise, print "Not Found".
Problem Description:
The given problem, wants you to find those indices from the first string from where if we find the substring of length equal to the second string then both the substring and second string are equal. If it is not possible to find any of the indices then you are asked to print "Not Found".
Input: The input line consists of a number of T test cases. Each test case has two strings A and B. Here |A|>|B|.
Output: For each case print the number (found pattern from the given string) next line their position. Otherwise, print 'Not Found'. There will a blank line between the two cases.
Example:
Input:
T=1
A=ababab B=ab
Output:
3
1 3 5
Explanation:
Since the pattern "ab" occurs at indices 1,3 and 5 so size is 3.
(1) Brute Force Approach:
In this approach, we will generate substring of length equal to the pattern and then match each character of the substring of with the pattern, if the substring matches with pattern then we add that index with our answer vector.
Program:
Output:
Enter number of test cases: 2
(2) Kmp Algorithm Approach:
In this approach, we will use Knuth Morris Pratt Algorithm. To use Kmp algorithm, we need to construct the longest prefix and suffix array i.e., lps array, to construct lps array we will use the following approach:
Here, we will use an array that represents the length of the longest proper prefix which is also equal to the suffix of the array.
Following are the steps that are involved in this approach:
We can get lps[] array with the help of two-variable len and i but to avoid confusion i used j variable here.
We also know that lps[j-1] is the count of characters of B[0…j-1] that are both proper prefix and suffix, thus we can conclude that we do not need to match these lps[j-1] characters with A[i-j…i-1] because we know that these characters will anyway match.
Program:
Output:
need an explanation for this answer? contact us directly to get an explanation for this answer