BUPT JAVA: 最大匹配最小匹配

最大匹配最小匹配

题目描述:

正则表达式, 又称规则表达式. (英语: Regular expression, 在代码中常简写为 regex, regexp 或 RE), 是计算机科学的一个概念.
正则表达式通常被用来检索, 替换那些符合某个模式 (规则) 的文本. 在正则表达式中通常有某个字符可以匹配若干个字符.
假设在某程序设计语言的正则表达式中 * 就可以匹配 0 个或多个字符. 比如 a*b可以匹配 ab, acb, adb, acdb, adkfjgjdkb等等.
在字符串 acbddbeeebff 中, 有多个字串可以和 a*b 匹配，包括 acb, acbddb, acbddbeeeb. 那么应该选哪个呢?
通常有两种策略可选, 一种是最小匹配, 就是选最短的 acb; 另一种是贪婪匹配, 就是选最长的 acbddbeeeb.
现在就请你写一段程序根据给定模式串和匹配串分别输出最小匹配和贪婪匹配的结果.

提示: java 语言可以用 Matcher 和 Pattern 类

输入:

为 2 行, 每行都是一个字符串, 字符串长度均大于 2 且小于 100. 第一行的字符串中包含且仅包含一个 *, 且这个 * 不会出现在字符串的开头, 为模式串.
也就是说这里的 * 可以匹配0个或多个任意字符. 第二行的字符串一定不包含 *, 为待匹配串.

输出:

也为 2 行, 每行都是一个字符串. 第一行为最小匹配的结果, 第二行为贪婪匹配的结果. 测试用例保证一定有解.
特别注意: 样例中的最小匹配是 aab 而不是 ab, 这种规则意味着我们在待匹配串中从前向后找模式串时, 当模式串 * 号前边的内容一旦与待匹配串中某部分匹配, 就不会再在待匹配串中后边的部分查找是否还有与之匹配的情况. 或者说此时我们找到了最大匹配与最小匹配在待匹配串中的共同的起始位置.

输入样例:

a*b
haabaaaabcd

输出样例:

aab
aabaaaab

Java

// 2023/04/04
// 最大匹配最小匹配
// 这个题理解错题意了, 需要对 "正则表达式" 有深刻的理解

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

public class Main {
    public static void main(String[] args) {
        var input = new Scanner(System.in);
        String regex = input.next(), str = input.next();
        String head = "", tail = "";
        for (int i = 0; i < regex.length(); i++)
            if (regex.charAt(i) == '*') {
                head = regex.substring(0, i);
                if (i + 1 <= regex.length())
                    tail = regex.substring(i + 1);
                break;
            }

        // 从网上查一查这种正则匹配串怎么写
        var minRegex = head + ".*?" + tail;
        var maxRegex = head + ".*" + tail;
        Pattern minPattern = Pattern.compile(minRegex), maxPattern = Pattern.compile(maxRegex);
        Matcher minMatcher = minPattern.matcher(str), maxMatcher = maxPattern.matcher(str);

        // 不用通过循环来查找最短或最长的串, 只需输出匹配成功的第一个匹配串即可.
        minMatcher.find();
        System.out.println(minMatcher.group());

        maxMatcher.find();
        System.out.println(maxMatcher.group());
    }
}

2023-04-04 
IP属地: 北京