算法|题解

HDU 6170 Two strings

凝神长老 · 2月20日 · 2019年 · · 1148次已读

本文写于 2019年02月20日,距今已超过 1 年,距 2020年03月27日 的最后一次修改也已超过 3 个月,部分内容可能已经过时,您可以按需阅读。如果图片无法显示或者下载链接失效,请给我反馈,谢谢!


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。

订阅评论动态
提醒
guest
0 评论
行内反馈
查看所有评论