Two strings

这道题是2017年ACM多校训练赛的题目，是一位ACM室友告诉我的，我觉得蛮好玩，就做了一下。

2017 Multi-University Training Contest – Team 9

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6170

题目大意就是给你一个字符串，再一个模式字符串，问你是不是能匹配。

这一听不就是正则表达式做的事情嘛……

模拟是可以做的，不过代码量比较大，需要注意的细节也比较多。

听说，“正解”是动态规划，场上过了的大多数都是DP过的，其他企图瞎分类讨论的大多WA了、企图用正则的时候却发现不怎么会写正则……

DP的思路是维护一个Boolean的二维数组，表示第二个字符串长度为x的情况下，且第一个字符串长度为y，能够匹配。

具体可以参考这篇文章：https://blog.csdn.net/jaihk662/article/details/77483118，以及，https://blog.csdn.net/weyoungg/article/details/77488030，代码量都不小。

我用正则表达式写了一下，代码量少，但是坑很多，主要原因是这道题不是纯粹的正则表达式，对*和.的处理是不一样的。

先给出代码。

import java.util.Scanner;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int t = in.nextInt();
        while (t-- != 0)
        {
            String input = in.next();
            String rawRegex = in.next();
            rawRegex = rawRegex.replaceAll("(.\\*)\\1{1,}", "$1");
            String[] s = rawRegex.split("\\.\\*");
            StringBuffer sb = new StringBuffer();
            for (int i = 0; i < s.length; i++) {
                sb.append(s[i]);
                if (i < s.length - 1)
                    sb.append("(.)\\" + (i + 1) + "*");
            }
            if (rawRegex.endsWith(".*"))
                sb.append("(.)\\" + (Math.max(s.length,1)) + "*");
            String regex = sb.toString();
            Pattern p = Pattern.compile(regex);
            Matcher m = p.matcher(input);
            System.out.println(m.matches() ? "yes" : "no");
        }
    }

}

然后解释一下。

这道题是正则表达式的题目，不过有点区别，所以我还是看了测试数据以后才把所有情况考虑进去的，一开始我用的是正则表达式直接判断的，不仅超时，还是错的。

主要原因是这道题不是纯粹的正则表达式，对*和.的处理是不一样的。

int t = in.nextInt();
while  (t--!=0) {
    String s = in.next();
    String regex = in.next();
    Pattern p = Pattern.compile(regex);
    Matcher m = p.matcher(s);
    if (m.matches()) {
        System.out.println("yes");
    } else {
        System.out.println("no");
    }
}

上面这段代码很清楚，就是读入一个input、读入一个regex，然后compile一下，去match。

注意是match，而不是find，要求的是整个字符串匹配，而不是存在部分匹配。

但是这段代码超时，并且答案也是错的。

首先解决错误。

看一种情况：.*如果是普通的匹配，是可以匹配sdfnjkwe的，因为.*意思就是任意字符匹配任意多次，可以是空串，或者.或者..或者.....等。

但是在这道题的意思是，.匹配了一个字母，假设是s，那么.*只能匹配到sssss，因为.*此时就变成了s*。

这是这道题和Regex不一样的地方，于是我们要把.*换成(.)\1*。

这里的括号是分组，表示.匹配到的那一个，\1是反向引用。

于是(.)\1*在上面的例子上就相当于s*。

String[] s = rawRegex.split("\\.\\*");

首先把.*给分出来，因为单独的.和*都是不影响的。

for (i = 0; i < s.length; i++) {
    sb.append(s[i]);
    if (i < s.length - 1)
        sb.append("(.)\\" + (i + 1) + "*");
}
if (rawRegex.endsWith(".*"))
    sb.append("(.)\\" + (i + 1) + "*");

然后利用StringBuffer把.*替换成(.)\$*，其中$指得是反向引用的编号，注意到最后一个如果是以.*结尾的，要加上，因为Split会吞掉。

还有一个问题是会超时。

比如用a*a*a*去匹配baaaa，显然瞬间就是不可能的，但是匹配aaaaab的话就要去看看再说。

于是为了满足贪婪匹配原则，就要不停地尝试，所以当比较短的时候还行，长了就不行了。

比如最后一组测试数据，就会导致TLE。

这时候我们考虑一个问题：a*a*和a*是一样的，a*a*a*和a*是一样的，即(.*)\1{1,}只要留下一个就行了。

但是怎么就留下一个呢？

我们可以试着全部去掉，这时候就算全部去完了也不要紧，比如a*a*a*和a*是一样的，而a*是可以匹配空串的，但是去掉以后如果变成空串了。

最后，给一个C++的用正则表达式做的链接：https://blog.csdn.net/xlzhang223/article/details/77487955。