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".

**I****nput:** 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.

O(n*m)O(n)Program:Output:(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.,

lpsarray, to constructlpsarray 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:

lps[]array which stores the length of the longest proper prefix which is equal to the suffix, each index oflpsrepresents the current indexlpsupto that index comparison. Initializelps[0]=0, since it is not possible to have proper prefix-suffix with one letter then we declare two variablejandiby which we compare the characters.We can get

lps[]array with the help of two-variablelenandibut to avoid confusioniusedjvariable here.longestprefixsuffix()which will take stringstras its parameter,lenvariable inside it will store the length of the given string, then we createlps[len]array withlps[0]=0as explained above, then we initialize indexito 1 andjto 0.ifrom 1 tolen -1and during each iteration, we comparestr[i]withstr[j]and check if both are equal or not. If equal then we incrementjby one and assignlps[i]tojand incrementi. Else if they are not equal then we search for that index whose character matches with the current character at indexi.j=0withB[j]andA[i]whereibegins from 0.{(A[i]==B[j])i++,j++}until we confront some mismatch.A[0..j-1]match withB[i-j…i-1](herejstarts with 0 and increment it only when there is a match).We also know that

lps[j-1]is the count of characters ofB[0…j-1]that are both proper prefix and suffix, thus we can conclude that we do not need to match theselps[j-1]characters withA[i-j…i-1]because we know that these characters will anyway match.O(n+m)O(n)Program:

need an explanation for this answer? contact us directly to get an explanation for this answerOutput: