问题描述

一道算法问题字符串匹配的

为了能有效地辅助对话系统完成限定领域完整对话流程，我们需要一个强大的匹配功能，现在要求你用编程来实现以下功能：
我们给出N个句子，作为语料库，语料库的句子分为以下三类：
1. 包含＂_＂，＂_＂可以匹配任意长度的字符串或者空串，例如，“早上好，店家！”能被语料库中的“_早上好_”匹配到，这类句子优先级最高。
2. 包含＂*＂，＂*＂可以匹配任意长度的字符串或者空串，例如，“早上好，店家！”能被语料库中的“*早上好*”匹配到，这类句子优先级最低。
3. 不包含＂_＂和＂*＂，这种句子要求完全匹配，例如，只有“早上好，店家！”能被语料库中的“早上好，店家！”匹配到，这类句子优先级居中。
不会有句子中同时出现＂_＂和＂*＂，也不会出现连续的＂_＂或者＂*＂，例如“__你好”和“**你好”或者“*你好_”这种句子是非法输入。
接下来有M句用户的输入，对于每一句输入，要求回答，语料库中能匹配到的句子，如果有多句匹配到了，请输出优先级最高的一句，如果优先级一样，请输出，除＂_＂和＂*＂外其他字符最多的，如果仍然有多句输出，请输出任意一句，详见输入样例。

输入:
第1行，输入一个整数Ｎ（Ｎ<=１００），表示语料库中的句子数
接下来N行，每行输入一个句子，表示语料库中的句子
第Ｎ＋２行，输入一个整数Ｍ（Ｍ＜=１００），表示用户都输入数
接下来M行，每行输入一个用户的句子
所有输入只包含＂_＂和＂*＂作为特别意义字符，常用中文标点符号，中文字符，以及数字，每个句子不超过１００字节。
输出：
M行
对于每个用户输入，按上述要求输出一个匹配到的句子，匹配不到输出＂匹配不到＂。

Sample　input１
３
早上好
早上好
早上好，店家！
２
早上好，店家！
早上好，小子！
Sample　output１
早上好
早上好

Sample　input２
３
早上好，
早上好
早上好，店家！
３
早上好，店家！
早上好
早上好，小子！
Sample　output２
早上好，店家！
早上好
早上好，

Sample　input３
３
早上好，*
早上好*
早上好，店家！
３
早上好，店家！
早上好
小子，早上好！
Sample　output３
早上好，店家！
早上好*
匹配不到

％２０的数据的语料库只包含第３类句子
％５０的数据的语料库只包含第１类和第３类句子
％１００的数据的语料库包含１，２，３类的句子

当Ｎ<＝５００００时，Ｍ<＝１００时，你所设计的算法时间复杂度是多少？如何实现高效，快速匹配。
当Ｎ<＝５００００时，Ｍ<＝１００００时，你所设计的算法时间复杂度是多少？如何实现高效，快速匹配。