字符串匹配系列问题 & NOI OJ 6252 带通配符的字符串匹配 题解

对于带通配符的字符串$A$和普通或者带通配符的字符串$B$,字符串中可能有星号$*$可以匹配0个或多个任意字符,还可能有问号$?$可以匹配正好一个字符,问字符串$A$和$B$是否相互匹配。
诸如此类的问题叫做字符串匹配问题,由它的解决方案扩展而成的正则表达式在生产开发中具有重要的意义。
这篇文章中,我们从NOI OJ 6252这道题引入,探讨解决这类问题的方法。

一个字符串带通配符的字符串匹配

请看题(NOI OJ 6252) http://noi.openjudge.cn/ch0206/6252/

题目大意就是,带通配符的字符串$A$和普通的字符串$B$长度都满足$al\le 20, bl\le 20$,$A$中可能有星号$*$可以匹配0个或多个任意字符,还可能有问号$?$可以匹配正好一个字符,问$B$是否能匹配字符串$A$。

这道题我刚拿到时是一脸懵逼的。不过研究题目后,我注意到了题目的特点:

  1. 问题可以分割为有意义的子问题。就是说,如果把字符串$A​$的前几个字符组成的子串$m​$,和$B​$中前几个字符组成的子串$n​$,把$m​$和$n​$单独挑出来替换题中的$A​$和$B​$,这个问题依然有意义。
  2. 问题没有后效性。就是说子串$m$和$n$是否有解,与$A$和$B$后半部分的字符无关。

思索再三看到了题目的分类是动态规划,我最后选择了动态规划来求解。

对于字符串$A$的第$i$个字符,有可能是星号、问号或者其它普通的字符。星号是最好处理的——末尾的星号意味着我们可以无视子串$n$剩下的部分。所以说如果有已经确认匹配的$m$和$n$字符串,在$m$后面加上一个星号形成$m’$,在$n$后面加上任意长度的任意字符串或者不加字符串形成$n’$,必有$m’$和$n’$依然匹配。

除了星号,问号和普通字符都只可以匹配1个字符,所以把他们放在一起考虑。普通字符的匹配规则是很显然的,如果两个字符相同那就匹配,那么对于已经确认匹配的字符串$m$和$n$,我们在$m$和$n$后面分别加上一个相同的字符,使他们成为$m’$和$n’$,那么$m’$和$n’$依然匹配。问号可以匹配任意的一个字符,那么将$m$加上一个问号变成$m’$,$n$加上任意的一个字符成为$n’$,一定有$m’$和$n’$匹配。

综上所述,对于任意已经确认匹配的字符串$m$和$n$,必定有以下匹配法则:

  1. $m$加一个星号,必定和$n$加上任意字符或不加字符匹配
  2. $m$加一个问号,必定和$n$加上任意一个字符匹配
  3. $m$加一个普通字符,必定和$n$加上相同的普通字符匹配

这时候我们就可以定义状态。如果把$A$的前$i$项字符组成的串记为$m$,把$B$的前$j$项组成的串记为$n$,那么就可以定义布尔数组$dp[i][j]$记为$m$和$n$是否匹配。根据上面的匹配法则,可以得出这样的递推法则:

  1. 如果A[i]是星号,只要${dp[i-1][k], 1\le k\le bl}$中有一个为真,那么$dp[i][j]$为真
  2. 如果A[i]是问号,而且$dp[i-1][j-1]$为真,那么$dp[i][j]$为真
  3. 如果A[i]是普通字符,而且$dp[i-1][j-1]$为真,而且A[i]B[j]相同,那么$dp[i][j]$为真

对于动态规划问题,我们还需要考虑边界条件。如果A、B是两个由一个相同普通字符组成的字符串,即$i=j=1$且 A[i]=B[j] ,显然$dp[1][1]$为真,按照递推法则3,必须要先有$dp[0][0]$为真——两个空的字符串我们不能认为他们不匹配。如果$A$只包含一个星号,即$i=1$且A[1]为星号,虽然我们得到了递推法则1,但我们似乎不能用赋初值的方法让$dp[0][k]$全部符合——那就特判一下吧。

这道题还有个坑的地方——字符串A和B可以包含空格!我一开始没有发现,然后用cin读入,自信满满的提交了代码以为能AC,结果WA了两组点,修改了用gets读入才得到AC。另外,这题数据范围不大,如果长度大还能用滚动数组优化空间复杂度,这里就不讲了。

AC代码是这样的:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
#define FOR(x,f,t) for(x=f;x<=t;++x)
#define M 25
char A[M], B[M];
bool dp[M][M];
int al,bl,i,j,k;
int main () {
gets(A+1), gets(B+1); //读入有空格!
al=strlen(A+1), bl=strlen(B+1);
dp[0][0]=1; //赋初值,上文有提到
if(A[1]=='*') FOR(j,0,bl) dp[1][j]=1; //特判,一个星号能匹配所有的字符串
FOR(i,1,al) {
if(A[i]=='*') FOR(j,1,bl) FOR(k,1,bl) dp[i][j]|=dp[i-1][k];
else FOR(j,1,bl) dp[i][j]=(dp[i-1][j-1]&&(A[i]==B[j]||A[i]=='?')); //这里把普通字符和问号合并了
}
if(dp[al][bl]) cout<<"matched";
else cout<<"not matched";
return 0;
}

其实这个问题还有个升级版——

两个字符串都带通配符的字符串匹配

不要给这标题吓到了。有了解决了一个字符串的通配符问题的经验,两个字符串都含通配符的匹配问题不是很难想。

当第二个字符串也出现通配符的时候,我们经过推敲,欣喜的发现的法则都没有变化——意味着我们的核心算法不需要做大的改动。唯一需要注意的是赋予初值时的小变化——赋予初值的时候注意把$A$和$B$都判断一次,判断星号问号的时候把$A$和$B$同时判断即可。

我们只需要对原来的代码做一些小更改,就能得到解决两个字符串都带通配符的匹配问题的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
#define FOR(x,f,t) for(x=f;x<=t;++x)
#define M 25
char A[M], B[M];
bool dp[M][M];
int al,bl;
int main () {
gets(A+1), gets(B+1);
al=strlen(A+1), bl=strlen(B+1);
int i,j,k;
dp[0][0]=1;
if(A[1]=='*') FOR(j,0,bl) dp[1][j]=1;
if(B[1]=='*') FOR(i,0,al) dp[i][1]=1; //同时赋初值
FOR(i,1,al) { //这里从A的长度作为第一维,其实从A和B都是一样的
if(A[i]=='*'||B[i]=='*') FOR(j,1,bl) FOR(k,1,bl) dp[i][j]|=dp[i-1][k]; //同时判断星号
else FOR(j,1,bl) dp[i][j]=(dp[i-1][j-1]&&(A[i]==B[j]||A[i]=='?'||B[i]=='?')); //同时判断问号
}
if(dp[al][bl]) cout<<"matched";
else cout<<"not matched";
return 0;
}

总结

字符串匹配问题的应用非常广。我们在生产开发过程中常常有各种各样的字符串匹配和替换需求,这时候就可以用到正则表达式(regexp或regex),这是一个比上面两个字符串匹配算法还要强大的引擎,许多编程语言都支持它,许多文本编辑器也使用它来完成查找替换。正则表达式辉煌的背后需要解决许多类似这样的字符串匹配问题,有兴趣的朋友们可以去百毒或者谷割了解一下。

最后感谢 KyleYoung神犇 的指导 :)

by lmlstarqaq