32.3-5带有通配符的匹配(自动机)
功能
这个程序可以判断一个带有通配符*的模式串是否在文本串中存在,没有记录位置信息,当然,想记录也是可以的
样例输入:
abccbacbababc
ab*bab*c
样例输出:
1思路
对于样例输入,有限自动机如图所示:
我们把每个通配符隔开的字串看做独立的,在其上运行KMP算法的comput_suffix_function过程,区别仅在于每部分的开头的fail指向上部分的结尾,每个部分的结尾fail指向自己(如果后面紧跟的一位匹配失败,由于通配符可以代替任意长度的任意字符串,不需要像KMP算法一样前移)
#include本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！