PROGRAMMING:Pattern matching of strings

Given two English alphabetic strings string and pattern, it is required to find the position where pattern first appears in the string and output the substring of the string after this position. If not found, output "not found".
The purpose of this paper is to test the performance of different matching algorithms under various data conditions. The characteristics of each group are as follows
-Data 0: small string, testing the basic correctness;
-Data 1: random data, string length is $$10 ^ 5 $$, pattern length is $$10 $$;
-Data 2: random data, string length is $$10 ^ 5 $$, pattern length is $$10 ^ 2 $$;
-Data 3: random data, string length is $$10 ^ 5 $$, pattern length is $$10 ^ 3 $$;
-Data 4: random data, string length is $$10 ^ 5 $$, pattern length is $$10 ^ 4 $$;
-Data 5: string length is $$10 ^ 6 $$, pattern length is $$10 ^ 5 $$; Test the end character mismatch;
-Data 6: string length is $$10 ^ 6 $$, pattern length is $$10 ^ 5 $$; Test for first character mismatch.
###Input format:
Input the first line to give string, which is a string composed of English letters and no longer than $$10 ^ 6 $. The second line gives a positive integer $$n $$($$Le 10 $$), which is the number of pattern strings to be matched. The next $$n $$line, each line gives a pattern, which is a string composed of English letters and no longer than $$10 ^ 5 $. Each string is not empty and ends with a carriage return.
###Output format:
For each pattern, the matching results are output according to the requirements of the questions.
###Input example:
```in
abcabcabcabcacabxy
three
abcabcacab
cabcabcd
abcabcabcabcacabxyz
```
###Output example:
```out
abcabcacabxy
Not Found
Not Found
```







answer：If there is no answer, please comment