【HDU-6170】解题报告（字符串，正则匹配，dp）

原始题目

Two strings

  • Time Limit: 2000/1000 MS (Java/Others)
  • Memory Limit: 65536/65536 K (Java/Others)
  • Total Submission(s): 2511
  • Accepted Submission(s): 891

Problem Description

Giving two strings and you should judge if they are matched.

  • The first string contains lowercase letters and uppercase letters.

  • The second string contains lowercase letters, uppercase letters, and special symbols: “.” and “*”.. can match any letter, and * means the front character can appear any times. For example, “a.b” can match “acb” or “abb”, “a*” can match “a”, “aa” and even empty string. ( “*” will not appear in the front of the string, and there will not be two consecutive “*”.

Input

The first line contains an integer T implying the number of test cases. (T≤15) For each test case, there are two lines implying the two strings (The length of the two strings is less than 2500).

Output

For each test case, print “yes” if the two strings are matched, otherwise print “no”.

Sample Input

3
aa
a*
abb
a.*
abb
aab

Sample Output

yes
yes
no

Source

2017 Multi-University Training Contest - Team 9

Recommend

liuyiding

题目大意

给定 \(a\)，\(b\) 两个字符串。\(a\)字符串只由字母构成，\(b\)字符串由字母和"."，"*"两种符号组合成。 有如下规则。 - "符号可以匹配任意一个字母。 - "*"符号可以匹配0个或多个上一字母，且不会出现在开头。 判断\(a\)，\(b\)两字符串能否匹配。

解题思路

改变了"*"规则的正则匹配。可以用C++正则匹配的库做，也可以使用dp做。

dp思路：bool型dp二维数组，\(dp[i][j]\)表示\(a\)字符串第i位和\(b\)字符串第j位能否匹配。

状态转移方程： - 当\(b_j\)为"."时，\(dp[i][j]=dp[i-1][j-1]\)。 - 当\(b_j\)为字母时，若\(a_i=b_j\)，则\(dp[i][j]=dp[i-1][j-1]\)。否则\(dp[i][j]=0\)。 - 当\(b_j\)为"*"时，根据"*"的规则。上一个字母出现次数为\(n\)。 - 当\(n=0\)时，匹配为上一个字母没有出现过，可从\(dp[i][j-2]\)转移过来。 - 当\(n=1\)时，匹配为上一个字母出现一次，可从\(dp[i][j-1]\)转移过来。 - 当\(n=2\)时，匹配为上一个字母出现两次，故若\(a\_i=a\_{i-1}\)时，可从\(dp[i-1][j-1]\)转移过来。否则\(dp[i][j]=0\)。 - 当\(n>2\)时，匹配为上一个出现\(n\)次，若\(a\_i=a\_{i-1}\)时，\(dp[i-1][j]\)转移过来，可以不断回退直到到上一情况。

解题代码

  1. 正则匹配法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <string>
#include <string.h>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <list>
#include <bitset>
#include <stack>
#include <stdlib.h>
#include <regex>
#define lowbit(x) (x&-x)
#define e exp(1.0)
#define eps 1e-8
//ios::sync_with_stdio(false);
//    auto start = clock();
//    cout << (clock() - start) / (double)CLOCKS_PER_SEC;
typedef long long ll;
using namespace std;
 
int main()
{
    ios::sync_with_stdio(false);
    int T;
    cin>>T;
    while(T--)
    {
        string a,b;
        cin>>a>>b;
        b=regex_replace(b,regex("\\.\\*"),"(.)\\1*");
        regex_match(a,regex(b))?cout<<"yes"<<endl:cout<<"no"<<endl;
    }
    return 0;
}

  1. dp 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    #include <bits/stdc++.h>
    using namespace std;
    #define rep(i,a,n) for (int i=a;i<n;i++)
    #define per(i,a,n) for (int i=n-1;i>=a;i--)
    #define pb push_back
    #define mp make_pair
    #define np next_permutation
    #define all(x) x.begin(),x.end()
    #define fi first
    #define se second
    #define INF Ox3f3f3f3f
    #define SZ(x) ((int)(x).size()) 
    //ios::sync_with_stdio(false);
    //    auto start = clock();
    //    cout << (clock() - start) / (double)CLOCKS_PER_SEC;

    const int maxn=2510;


    char a[maxn],b[maxn];
    bool dp[maxn][maxn];
    int n,m;
    int main(){

    	int TT,T=0;
    	scanf("%d",&TT);
    	while(TT--){
    		scanf("%s",a+1);
            scanf("%s",b+1);
            n=strlen(a+1);
            m=strlen(b+1);
            memset(dp,0,sizeof(dp));
            dp[0][0]=1; if (b[2]=='*') dp[0][2]=1; 
            for(int i=1;i<=n;i++){
            	for(int j=1;j<=m;j++){
            		//字母情况 
            		if(b[j]!='.'&&b[j]!='*'){
            			dp[i][j]=(a[i]==b[j]?dp[i-1][j-1]:0);
    				}
    				else if(b[j]=='.'){
    					dp[i][j]=dp[i-1][j-1];
    				}
    				else if(b[j]=='*'){
    					dp[i][j]=dp[i][j-1]|dp[i][j-2];
    					if(a[i]==a[i-1]&&!dp[i][j]) dp[i][j]=dp[i-1][j-1]|dp[i-1][j]; 
    					//注意此处!dp[i][j] 否则会将状态由1更新为0，诸如 bb  bba*就会出错 
    				}
    			}
    		}
    		
    		if(dp[n][m]) printf("yes\n");
    		
    		else printf("no\n");
    		
    			
    	}
    	return 0;
    }
    //1
    //bb
    //bba*

收获与反思

  • C++正则匹配regex库，涨姿势。
  • 字符串dp，状态转移的思考需要学习一下。