hello friends and welcome to geeks for geeks in this tutorial we will learn:about naive algorithms for patent searching problem statement given a text ring of size n and a pattern string of size M we need to write a function search that takes us input the text and pattern string and prints all occurrences of pattern in the text string it is given that the text ring size n is always greater than the pattern string size M for example if I have text this and the pattern string there is then the output should print the indexes in text string where the pattern string is found like a ap a is found starting from index 0 of text string then starting from index 9 and then starting from next one so this should be printed in our output so if I have text string of size 16 and pattern string of size 4 then I need to take a window size of 4 which is the size of pattern string now we start running the window over the text string starting from index 0 this is the window in text string then we compare this window with the pattern string and if both these strings are found to be equal then we say that the pattern has been found at that particulars index in text string then we move the window forward and again compare the window with the pattern string similarly we keep moving the window until we reach to the last window this is the last window in text string so we see that if text string size is 16 and the pattern string size is 4 then the last index where the window should be there is given by 16 minus 4 that is 12 so the window runs from 0 to 12 so there should be an outer loop in the code which runs for n minus M time this indicates the starting index of the window any size of the text ring and M size of the pattern string then for each window there is an inner loop which runs from 0 to M that is the size of the pattern string and then compares the window with the pattern coming on to the code this code is taken from geeks for geeks the search function takes as input the text and pattern string and then computes and stores their length in M and M then there is outer loop from 0 till less than equals to n minus M which represents the window starting index then for each window there is an inner loop which runs from 0 till less than M and compares pattern and the current window if at any point we do not find a match we break so and at last we see whether the upper loop run for the whole time if there is a match then we blend pattern found at index I that is the starting index of the window best case what the problem is fen the first character of the pattern is not present in this text ring at all for example if text ring is this and a pattern string is this then the first character of the pattern is not at all present in this text ring so our task is just to move the window one by one over the text ring and then we just need to come need to come need to compare the first character of the current window and the string so the time complexity is equals to the number of windows which is n minus M so the time complexity is big off in the worst case has been all characters of the text and pattern are same then for each window I need to compare all the characters in pattern with the window or otherwise even if only the last character is different that is like hair be then also I need to compare the whole window with the pattern string so here in the worst case the time complexity is number of windows multiplied by the window size which is Big O of M into n minus m plus 1 the KNP matching algorithm improves the worst case to Big O of n the KMP algorithm is covered in a separate video thank you for watching please leave us your likes and comments