-1

条件：

  1. 有很多规则，可能有数百条，例如：
    {aab*, aabc*, aabcdd*, dtctddds*, *ddt*, *cddt*, *bcddt*, *t, *ttt, *ccddttt}

  2. 每次我会得到一个字符串，那么我应该找到最长的匹配规则。

例子：

示例 1.string 是aabcddttt匹配的规则应该是：aabcdd*

示例 2. string 是accddttt匹配的规则应该是*ccddttt

问题： 我不想用长数组中的规则来一一匹配字符串，这是低效的方法。也许我应该使用字符串作为正则表达式来匹配一百条规则。但是我找不到一个优雅的方式来解决这个问题。

  1. 我可以使用一些正则表达式来获得结果吗？
  2. 哪种匹配方式最好/最快？

首选 Java、纯 C 或 shell，请不要使用 C++ STL

4

2 回答 2

1

最长公共子串

也许这个算法就是你要找的=）。

为什么不简单地做呢？

String[] rules = {"^aab", "bcd", "aabcdd$", "dtctddds$", "^ddt$", "^cddt$", "^bcddt$", "^t", "^ttt", "^ccddttt"};
        String testCase = "aabcddttt";

        for (int i = 0; i < rules.length; i++) {
            Pattern p = Pattern.compile(rules[i]);
            Matcher m = p.matcher(testCase);
            if (m.find()) {
                System.out.println("String: " + testCase + " has matched the pattern " + rules[i]);
            }
        }

所以基本上在这种情况下，rules[0]，它是 ^aab 找到的，因为胡萝卜 (^) 意味着字符串必须以 ^aab 开头。另一方面，bba$ 表示字符串必须以 bba 结尾。并且找到了规则1，因为这意味着该规则可以出现在 testCase 的任何位置（例如 bcd）。

于 2013-01-18T10:33:46.887 回答
0

您可以尝试一次将它们全部匹配，并在每个子规则周围加上括号。您可以使用该组来确定哪个匹配。

public static void main(String... ignored) {
    for (String test : "aabaa,wwwaabcdddd,abcddtxyz".split(",")) {
        System.out.println(test + " matches " + longestMatch(test, "aab*", "aabc*", "aabcdd*", "dtctddds*", "ddt"));
    }
}

public static String longestMatch(String text, String... regex) {
    String[] sortedRegex = regex.clone();
    Arrays.sort(sortedRegex, new Comparator<String>() {
        @Override
        public int compare(String o1, String o2) {
            return o2.length() - o1.length();
        }
    });
    StringBuilder sb = new StringBuilder();
    String sep = "(";
    for (String s : sortedRegex) {
        sb.append(sep).append('(').append(s).append(')');
        sep = "|";
    }
    sb.append(")");
    Matcher matcher = Pattern.compile(sb.toString()).matcher(text);
    if (matcher.find()) {
        for (int i = 2; i <= matcher.groupCount(); i++) {
            String group = matcher.group(i);
            if (group != null)
                return sortedRegex[i - 2];
        }
    }
    return "";
}

印刷

aabaa matches aabc*
wwwaabcdddd matches aabcdd*
abcddtxyz matches ddt
于 2013-01-18T10:32:12.110 回答