2 u010510549 u010510549 于 2013.11.29 20:57 提问

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

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

输入:
第1行,输入一个整数N(N<=100),表示语料库中的句子数
接下来N行,每行输入一个句子,表示语料库中的句子
第N+2行,输入一个整数M(M<=100),表示用户都输入数
接下来M行,每行输入一个用户的句子
所有输入只包含"_"和"*"作为特别意义字符,常用中文标点符号,中文字符,以及数字,每个句子不超过100字节。
输出:
M行
对于每个用户输入,按上述要求输出一个匹配到的句子,匹配不到输出"匹配不到"。

Sample input1

早上好
早上好
早上好,店家!

早上好,店家!
早上好,小子!
Sample output1
早上好
早上好

Sample input2

早上好,
早上好
早上好,店家!

早上好,店家!
早上好
早上好,小子!
Sample output2
早上好,店家!
早上好
早上好,

Sample input3

早上好,*
早上好*
早上好,店家!

早上好,店家!
早上好
小子,早上好!
Sample output3
早上好,店家!
早上好*
匹配不到

%20的数据的语料库只包含第3类句子
%50的数据的语料库只包含第1类和第3类句子
%100的数据的语料库包含1,2,3类的句子

当N<=50000时,M<=100时,你所设计的算法时间复杂度是多少?如何实现高效,快速匹配。
当N<=50000时,M<=10000时,你所设计的算法时间复杂度是多少?如何实现高效,快速匹配。

Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!