Write a C program, problem2.c, with search function to search for a substring within a string that returns -1 if the substring is not found and the position in the string if found. The search function only takes the substring and string as its formal parameters. Implement the search function with the brute force method given below. Alternatively, you can implement the search function with the suggested optimization given below. The main function should test the search function to demonstrate substrings are not found if not present in the string even if similar characters are at either end of the string or in the middle, can be found at the string beginning or end, and can be found in the middle of the string. No string.h functions may be used.

In comments at the end of the program, note i. the output for the program ii. Suppose the substring of size m occurs at the end of a size n string, then, 1. what would be a worst-case string and substring example for the brute force string search and what would be the Big O time complexity for the worst case? 2. what would be the best-case string and substring example for the optimized string search and what would be the Big O time complexity for the best case?