-1

条件：

  1. 多くのルール、おそらく数百のルールがあります。
    {aab*, aabc*, aabcdd*, dtctddds*, *ddt*, *cddt*, *bcddt*, *t, *ttt, *ccddttt}

  2. 文字列を 1 つ取得するたびに、最長一致ルールを見つける必要があります。

例:

例 1.string はaabcddttt一致するルールです。aabcdd*

例 2. string はaccddttt一致するルールです。*ccddttt

質問: 文字列を 1 つずつ照合するために長い配列のルールを使用したくありません。これは非効率的な方法です。文字列を正規表現として使用して、100 のルールを照合する必要があるかもしれません。しかし、まだ見つかりません。この問題を解決するエレガントな方法。

  1. 結果を得るためにいくつかの正規表現を使用できますか?
  2. 一致する最良/最速の方法はどれですか?

Java、プレーン C、またはシェルが推奨されます。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 に答える