如何使用动态编程增强正则表达式匹配

Question

我无法使用动态编程使这段代码更有效。我尝试过记忆和其他一些技术，但是当我修改此处的代码以使其在匹配时更有效时，我不断收到越界错误。有人对如何将动态编程方法应用于此方法有任何建议，以便它更有效地匹配吗？

public static int[][] getMatchingIndices( String[] regexes, String text, int flags ){
    //System.out.println("getMatchingIndices(regexes,"+text+","+flags+")");
    int[][] matches = new int[regexes.length][2];

    // initalize index for starting search position
    int startingSearchIndex = 0;

    // for each regex
    for(int regexI = 0; regexI < regexes.length; ++regexI){
        String regex = regexes[regexI];

        // search for first match (using flags)
        Pattern p = Pattern.compile(regex, flags);
        Matcher m = p.matcher(text.substring(startingSearchIndex));
        // record match (if found)
        int matchStartIndex = -1;
        int matchEndIndex = -1;
        if( m.find() ){
            //System.out.println(m);
            matchStartIndex = m.start() + startingSearchIndex;
            matchEndIndex = m.end() - 1 + startingSearchIndex;
            //System.out.println( "Searched for " + regex + " and found "+text.substring(matchStartIndex,matchEndIndex+1));

            // update starting search position
            startingSearchIndex = matchEndIndex + 1;
        }
        matches[regexI][0] = matchStartIndex;
        matches[regexI][1] = matchEndIndex;
    }
    return matches;
}

尝试了各种动态规划方法，但总是出现越界错误。

Answer 1

到目前为止，如果不提供引发异常的输入，就很难查明问题所在。

但是，我已经可以看到更新变量

startingSearchIndex

的部分处理得不好。方法

Matcher.end()

已经返回匹配后的字符 after。当你分配的时候

// update starting search position
startingSearchIndex = matchEndIndex + 1;

您正在跳过一个额外的字符。正如

Matcher.end()

文档所述：

返回最后一个匹配字符之后的偏移量。

您应该将该代码替换为：

// update starting search position
startingSearchIndex = matchEndIndex;