Two strings HDU

Two strings

题意：给两个串s和p，问是否能匹配。其中p里面有两个特殊字符，'.'可以匹配任意字符，'*'可以让前一个字符出现任意次。

dp~

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 const int maxn=2510;
 5 char s[maxn],p[maxn];
 6 int lens,lenp;
 7 int dp[maxn][maxn];
 8 int main(){
 9     int t;
10     scanf("%d",&t);
11     while(t--){
12         scanf("%s%s",s+1,p+1);
13         lens=strlen(s+1);
14         lenp=strlen(p+1);
15         memset(dp,0,sizeof(dp));
16         dp[0][0]=1;
17         for(int i=1;i<=lenp;i++){
18             if(p[i]=='.'){
19                 for(int j=1;j<=lens;j++){
20                     if(dp[i-1][j-1]) dp[i][j]=1;
21                 }
22             }else if(p[i]=='*'){
23                 for(int j=1;j<=lens;j++){
24                     if(dp[i-1][j-1]){
25                         dp[i][j-1]=1;
26                         if(j>=2) dp[i][j-2]=1;
27                         if(s[j]==s[j-1]) {
28                             dp[i][j]=1;
29                             while(s[j+1]==s[j]) dp[i][j+1]=1,j++;
30                         }
31                     }
32                 }
33             }else{
34                 for(int j=1;j<=lens;j++){
35                     if(!dp[i-1][j-1]) continue;
36                     if(p[i]==s[j]) dp[i][j]=1;
37                     else if(p[i+1]=='*') dp[i+1][j-1]=1;   //!!
38                 }
39             }
40         }
41         if(dp[lenp][lens]) puts("yes");
42         else puts("no");
43     }
44     return 0;
45 }

View Code

也可以直接用正则，转自http://www.cnblogs.com/shuiming/p/7413726.html

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <string>
 4 #include <regex>
 5 using namespace std;
 6 int main(){
 7     int cas;
 8     scanf("%d",&cas);
 9     string s1,s2;
10     while(cas--){
11         cin>>s1>>s2;
12         s2=regex_replace(s2,regex("\.\*"),"(.)\1*");
13         printf(regex_match(s1,regex(s2))?"yes
":"no
");
14     }
15     return 0;
16 }

View Code