**I DO NOT NEED THE ACTUAL CODE**

I need answers to this follow up question:

d. 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?

2. 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. a. A brute force way to find a substring within another is to search a string one character at a time until a character matches the first character of the substring as in the example shown below. i. Find sub = "carrot" in s = "Bob likes cars and carrots" 1. Compare B to c-mismatch 2. Compare o to c-mismatch 3. Compare b to c-mismatch 4. Compare space to c-mismatch 5. 6. Compare space to c-mismatch 7. Compare c to c-match (at "cars" in s) 8. Compare a to a-match 9. Comparer tor-match 10. Compares tor-mismatch, start back at the "a" in "cars" 11. Compare a to c-mismatch 12. Comparer to c-mismatch 13. Compare s to c-mismatch 14. Compare space to c-mismatch 0 15. - 16. Compare c to c-match 17. Compare a to a-match 18. Comparer tor-match 19. Comparer tor-match 20. Compare o to o-match 21. Compare t tot-match 22. Return location 19 in s Texas Tech University Whitacre College of Engineering ii. Think about how to optimize the search so the search algorithm does not have to go back to the "a" in "cars" on a mismatch, such as 1. Compare B to c-mismatch 2. 3. Compare to c-match 4. Compare a to a-match 5. Comparer tor-match 6. Compares tor-mismatch (since "e" was not encountered again, start at the space after "cars") 7. Compare space to c-mismatch b. Example output for the brute force search function: i. Search for 'carrot in 'carro carro carro carro'-location-1 ii. Search for 'carrot' in 'carrot carro carro carro' - location o iii. Search for 'caccoc' in 'cacco cacco caccoc cacco' - location 12 c. Example output for the optimized search function with a trace of the i index variable that traverses strings: i. substring - i = 0 ii. substring-i6 iii. substring - i 12 iv. substring - 1 = 18