题意
字符串模式匹配,'.'匹配任何一个字符,'*'表示它的前一个字符可以任意出现(0次或多次),给出字符串和模式串,询问是否匹配
分析
和标准正则表达式不同的是".*"模式串在题意下不能匹配"abcde"这样的字符串
按题意".*"的意思是相同字符的0个或多个重复串
那么我们把模式串中的".*"替换成"(.)\1*"即可
队友用其他的dp做法比较快,90ms,用c++库的正则表达式要600+ms
代码
(使用g++)
#include <iostream> #include <cstdio> #include <string> #include <regex> using namespace std; int main(){ int cas; scanf("%d",&cas); string s1,s2; while(cas--){ cin>>s1>>s2; s2=regex_replace(s2,regex("\\.\\*"),"(.)\\1*"); printf(regex_match(s1,regex(s2))?"yes\n":"no\n"); } return 0; }