问题 A: SkrSkr! [Easy] Solution

题目描述







Hong likes the Rap of China. He has tried to write some lyrics. However, he didn’t know how to judge a lyric. He thought that the more rhymes the better. The score of a lyric is equal to the length of the longest continued rhyming sentences. Two sentences are rhyming when the last letters of them are equal. Hong wants to know the score of the given lyrics.




输入







The first line will be an integer T (1≤T≤100), which is the number of test cases.




For each test data:




The first line contains an integer N (1≤N≤10^4) — the number of the sentences.




Each of the next N lines contains a string s, which consists only of lowercase letters (no space). The length of each string doesn’t exceed 100.




输出







For each case please, print the length of the longest continued rhyming sentences.




样例输入










1




5




nikanzhegemian




tayouchangyoukuan




jiuxiangzhegewan




tayoudayouyuan




skrskr




样例输出










4

问题 B: Matching Problem [Easy]







题目描述







Hong haves two strings s and t. The length of the string s equals n, the length of the string t equals m. The string s consists of lowercase letters and at most one wildcard character '*', while the string t consists only of lowercase letters.




The wildcard character '' in the string s (if any) can be replaced with an arbitrary sequence (possibly empty) of lowercase letters. If it is possible to replace a wildcard character '' in s to obtain a string t, then the string t matches the pattern s.




If the given string t matches the given string s, print "YES", otherwise print "NO".




输入







The first line will be an integer T (1≤T≤10), which is the number of test cases.




For each test data:




The first line contains two integers n and m (1≤n, m≤2⋅10^5) — the length of the string s and the length of the string t, respectively.




The second line contains string s of length n, which consists of lowercase letters and at most one wildcard character '*'.




The third line contains string t of length m, which consists only of lowercase letters.




输出







For each test cases, print "YES" (without quotes), if you can obtain the string t from the string s. Otherwise print "NO" (without quotes).




样例输入










1




10



aba*aba abazzzzaba




样例输出










YES

问题 C: Kate Make Program [Easy]







题目描述







Give you a text S and a pattern P. You should print how many times P appears in S.




输入







The first line will be an integer T, which is the number of test cases. (1 <= T <= 10)




For each test case, the first line will be an integer n, which is the length of the text string. Then a line contains a text string S. |S| <= 1000000




The third line will be an integer m, which is the length of the pattern string.




Then a line contains a pattern string P. |P| <= |S|




S and will only contain lower case English letters.




输出







Print a number in a single line for each test case, which means how many times P appears in S.




样例输入










2




15




chenljnbwowowoo




2




wo




14




touristrealgod




7




tourist




样例输出










3




1




提示







Easy problem.

问题 D: A Skr Song [Medium]







题目描述







Hong has learned something about music. He finds that punchline is very important. If a substring appears 3 times at the beginning, the middle, and the end of a lyric, the substring is a punchline. But it’s hard for Hong to find a punchline. He wants you to help him to find the longest punchline in a song.




输入







The first line will be an integer T (1≤T≤100), which is the number of test cases.




For each test data:




The first line contains an integer n (1≤n≤10^5) — the length of the string s.




The second line contains string s of length n, which consists only of lowercase letters, which is the lyric.




输出







For each case, please print the length of the longest punchline.




样例输入










2




6




ababab




7




abababa




样例输出










2




1

问题 E: Presuffix [Medium]







题目描述







A prefix of a string S is S0,i, similarly, a suffix of a string S is Si,|s|-1. Hong has two strings S and T, finds the longest prefix of S that is a suffix of T.




输入







The first line will be an integer T (1≤T≤50), which is the number of test cases.




For each test data:




The first line contains two integers n and m (1≤n, m≤10^5) — the length of the string S and the length of the string T, respectively.




The second line contains string s of length n, which consists only of lowercase letters.




The third line contains string t of length m, which consists only of lowercase letters.




输出







For each case, please print the length of the longest prefix of S that is a suffix of T, followed by the prefix.




样例输入










1




5 abc bcbab



样例输出










2 ab




问题 F: Longest Common Substring [Hard]







题目描述
There is a well-known problem called LCS, which is longest common subsequence. But it’s hard for Hong to find the longest common substring of N different string. Hong wants you to solve this question.




输入







The first line will be an integer T (1≤T≤10), which is the number of test cases.




For each test data:




The first line contains an integer N (1≤N≤1000) — the number of the sentences.




Each of the next N lines contains a string s, which consists only of lowercase letters (no space), the length of each string will be at least 1 and at most 200 characters.




输出







For each case please print the lexicographically smallest longest common substring. If there is no such non-empty string, output the words “Hong” instead.




样例输入










1




3




aabbaabb




abbababb




bbbbbabb




样例输出










abb







问题 G: Typer [Hard]







题目描述







Given n words, Hong wants to input one of these. He wants to input (at the end) as few characters (without backspace) as possible, to make at least one of the n words appears (as a suffix) in the text.




Given an operation sequence, Hong wants to know the answer after every operation.




An operation might input a character or delete the last character.

输入







The first line contains one integer n.




In the following n lines, each line contains a word.




The last line contains the operation sequence.




'-' means backspace and will delete the last character he typed.




He may backspace when there are no characters left, and nothing will happen.




1 <= n <= 4




The total length of n words <= 100000




The length of the operation sequence <= 100000




The words and the sequence only contain lower case letter.




输出







You should output L +1 integers, where L is the length of the operation sequence.




The i-th(index from 0) is the minimum characters to achieve the goal, after the first i operations.




样例输入










2




a




bab




baa-




样例输出










1




1




0




0




0




提示
















he need input "a" to achieve the goal. "b" he need input "a" to achieve the goal.



"ba" he need input nothing to achieve the goal. "baa" he need input nothing to achieve the goal.

"ba" he need input nothing to achieve the goal.