Last time you helped Orange Cat complete his puzzles. This time, he wants to arrange these puzzles on his shelf. He has a particular fondness for a specific pattern, represented here by a string S of length m. The more times this pattern S appears as a substring within a puzzle, the more he likes it! We'll call the number of occurrences of S the preference level.
Please help rearrange these n puzzles (P1 to Pn) by sorting them in descending order based on their preference levels. If two puzzles have the same preference level, maintain their original relative order.
The first line contains two positive integers n and m.
The following n lines each contain a string Pi.
The last line contains a string S of length m.
Subtasks
Output n lines, where the i-th line contains a string representing the puzzle placed in the i-th position.
Please remember to print "\n" at the end, and dont print space (" ") at the end of every line
Hint1:
Please implement string swapping in bubble sort using strcpy to avoid TLE (Time Limit Exceeded).
Hint2:
For testcases 5 ~ 6, please refer to the following polynomial. This technique is called rolling hash, which converts a string into a number within a fixed range, allowing string comparison in O(1) time:
(a1 * mn-1 + a2 * mn-2 + a3 * mn-3 + ... + an-1 * m1 + an * m0) mod P (m is a small prime number like 37, P is a big prime number like 109 + 7)
more reference: