- Functional Programming
- Functional Structures
- Substring Searching
In 1974, a very fast string searching method was proposed by the name of KMP algorithm with linear run-time complexity. Your task here is to code this (or any similar) algorithm in a functional language.
Given two strings text and pat, find whether pat exists as a substring in text.
First line will contain an integer, T, which represents total number of test cases. Then T test cases follow. Each case will contains two lines each containing a string. First line will contain text while the second line will contain pat.
For each case print
YES if pat is a substring of text otherwise
1 ≤ T ≤ 10
1 ≤ |pat| ≤ |text| ≤ 100000
All characters in text and pat will be lowercase latin character ('a'-'z').
4 abcdef def computer muter stringmatchingmat ingmat videobox videobox
YES NO YES YES
Test Case #00: Here "def" is present at the end of "abcdef".
Test Case #01: Though "muter" is a subsequence here, but we need it to be asubstring.
Test Case #02: _"ingmat"_ is present at index 3 and 11.
Test Case #03: Both strings are same.