bookmark_borderdescriptionGiven 2 strings A and B, find the number of occurrences of A in B as a substring.Note:Solve using the KMP string matching algorithm. Do not use an inbuilt library.Input FormatThe first line of input contains T - the number of test cases. It's followed by T lines. Each line contains 2 strings - A and B, separated by space.Output FormatFor each test case, print the number of occurrences of A in B, separated by a new line.Constraints1 <= T <= 20001 <= len(A), len(B) <= 10005'a' <= A[i], B[i] <= 'z'ExampleInput4smart yekicmsmartplrplsmartrplplmrpsmartrpsmartwmrmsmartsmartinterviews interviewseiwcombvinterviewskrenlzpds dsdsajdsrjjdsjjjalgo yalgoalgoalgopalgoaxalgoasaxalgolalgoalgoalgoOutput6249

Converting AnagramsMax Score: 100Given two strings A and B, find the minimum number of characters that need to be deleted from these 2 strings to make them anagrams of each other.Input FormatThe first line of input contains T - the number of test cases. It's followed by T lines, each line contains 2 space separated strings - A and B.Output FormatFor each test case, print the minimum number of deletions, separated by a new line.Constraints1 <= T <= 10001 <= len(A), len(B) <= 1000'a' <= A[i], B[i] <= 'z'ExampleInput2smart interviewsdata structuresOutput912ExplanationSelf Explanatory

Given 2 strings A and B, find the smallest substring of B having all the characters of A, in any order.Input FormatThe first line of input contains T - the number of test cases. It's followed by T lines, each line containing 2 space-separated strings - A and B.Output FormatFor each test case, print the length of the smallest substring of B having all the characters of A, separated by newline. If no such substring is found, print -1.Constraints20 points1 <= T <= 1001 <= size(A), size(B) <= 10060 points1 <= T <= 1001 <= size(A), size(B) <= 1000120 points1 <= T <= 1001 <= size(A), size(B) <= 10000General Constraints'a' <= A[i], B[i] <= 'z'ExampleInput4fkqyu frqkzkruqmfqyuzlkygonmwvytbytn uqhmfjaqtgngcwkuzyamnerphfmwbloets lwbcrsfothplxseplrtbshbtstjloxsfdzpd dclzztpjldkndgbdqqzmbpOutput7-1139ExplanationTest Case 1:The smallest substring containing all characters of A is "fqyuzlk", which has a length of 7.Test Case 2:Despite considering all possible substrings of B, we cannot find any substring containing all characters of A.Test Case 3:The smallest substring containing all characters of A is "bcrsfothplxse", which has a length of 13.Test Case 4:The smallest substring containing all characters of A is "ztpjldknd", which has a length of 9.

Understand the problem statement from the given sample input and output.Input FormatThe first line of input contains T - the number of test cases. It's followed by T lines, each line contains 2 strings A and B, separated by space, consisting only of lowercase English alphabets.Output FormatFor each test case, print the desired output, separated by a new line.Constraints10 points1 <= T <= 1001 <= len(A), len(B) <= 10040 points1 <= T <= 10001 <= len(A) <= 50001 <= len(A), len(B) <= 5000ExampleInput2data structuressmart interviewsOutputsrucuresineview

Write down the pseudocode of the Naïve string matching problem and apply both naïve and KMP tofind how many comparisons are required to find the match in the given text and patternText: AACBBABXYABBACAYXACABAAXBYACBYAAXBAAPattern: CABAAXBYA

In this challenge, the user enters a string and a substring. You have to print the number of times that the substring occurs in the given string. String traversal will take place from left to right, not from right to left.NOTE: String letters are case-sensitive.Input FormatThe first line of input contains the original string. The next line contains the substring.ConstraintsEach character in the string is an ascii character.Output FormatOutput the integer number indicating the total number of occurrences of the substring in the original string.Sample InputABCDCDCCDCSample Output2ConceptSome string processing examples, such as these, might be useful.There are a couple of new concepts:In Python, the length of a string is found by the function len(s), where is the string.To traverse through the length of a string, use a for loop:for i in range(0, len(s)): print (s[i])A range function is used to loop over some length:range (0, 5)Here, the range loops over to . is excluded.