Java:查找字符串之间的匹配项

Question

给定 2 个字符串，我想找到至少四个字符的第一个匹配项。

这是我目前必须执行的代码。它工作正常，但我认为可能有更好的方法来做到这一点。我所做的事情是否存在效率低下或不良做法？是否存在我应该利用但我没有利用的通用库，例如​​ Apache Commons？

不必担心 Gene 类 - 它只包含有问题的字符串。另外 - GeneMatch() 表示不存在匹配项，而带有参数的 GeneMatch 构造函数表示已找到匹配项。

Constants.MIN_MATCH == 4，在本例中。

public static GeneMatch findMatch(Gene g0, Gene g1) {

    String g0DNA = g0.getDNA();
    String g1DNA = g1.getDNA();

    if (g0DNA.equals("") || g1DNA.equals("")) { //there won't be a match if one is empty
        return new GeneMatch();
    }

    int g0Left = -1;
    int g0Right = -1;
    int g1Left = -1;
    int g1Right = -1;

    String window;

    for (int inx = 0; inx <= g0DNA.length() - Constants.MIN_MATCH; inx++) {
        window = g0DNA.substring(inx, inx + Constants.MIN_MATCH);

        if (g1DNA.indexOf(window) != -1) {

            g0Left = inx;
            g0Right = inx + Constants.MIN_MATCH;

            g1Left = g1DNA.indexOf(window);
            g1Right = g1Left + Constants.MIN_MATCH;

            /* grow the match to the right
             * while the two right indices are less than the lengths of their respective strings, and the 
             * characters at the indices match, increment each index
             */
            while (g0Right < g0DNA.length() && g1Right < g1DNA.length() && g0DNA.charAt(g0Right) == g1DNA.charAt(g1Right)) {
                g0Right++;
                g1Right++;
            }
            break; //we've already found a match, no need to continue sliding the window
        }
    }

    //now that the indices are found, convert to Genes
    if (g0Left == -1 || g0Right == -1 || g1Left == -1 || g1Right == -1) { //no match found
        return new GeneMatch();
    }

    Gene gL0 = new Gene(g0DNA.substring(0, g0Left));
    Gene gL1 = new Gene(g1DNA.substring(0, g1Left));

    Gene g0match = new Gene(g0DNA.substring(g0Left, g0Right));
    Gene g1match = new Gene(g1DNA.substring(g1Left, g1Right));

    Gene gR0 = new Gene(g0DNA.substring(g0Right));
    Gene gR1 = new Gene(g1DNA.substring(g1Right));

    //sanity check
    assert g0DNA.equals(gL0.getDNA() + g0match.getDNA() + gR0.getDNA()) : "g0 didn't add up";
    assert g1DNA.equals(gL1.getDNA() + g1match.getDNA() + gR1.getDNA()) : "g1 didn't add up";

    return new GeneMatch(gL0, gR0, g0match, g1match, gL1, gR1);

}

Answer 1

当前方法

1. 两次g1DNA.indexOf(window)调用 - 第一次调用结果可以存储并稍后重用；
2. 不必要的字符串对象窗口期间的施工 =g0DNA.substring(inx, inx +常量.MIN_MATCH);
3. 不必要的 gL0、gL1、gR0、gR1案例断言的构造是关闭；
4. if (g0DNA.equals("") || g1DNA.equals("")) 检查可以是改进以检查字符串至少有四个符号每个；
5. 调用 equals() 总是更好恒定，即使用"".equals(arg)。如果 arg 为 null，它可以避免可能的 NPE。它这里没有太大影响，只是良好的编码政策；
6. 有String.isEmpty()方法可以用来替换"".equals(arg);
7. 不执行 null 检查DNA 串；

改进

1. 最好循环最短字符串，即您应该检查 dna1和 dna2 长度并执行外部与较短的一个循环长度。这可以最大限度地减少迭代次数；
2. 您可以避免创建新的字符串对象并根据人物进行操作。此外，您还可以修改算法以便与任何java.lang.CharSequence实现；
3. 你可以记住无与伦比的序列，即保留字符集已检查的序列和被证明是无与伦比的最小化外循环时间迭代。例如你迭代在包含许多的字符串上'b' 个字符。您检查第二个字符串是否不包含该内容第一次'b'处理期间的字符。你可以记住这一点并停止后续'b'处理热切地；
4. 当您使用String.indexOf()时搜索从开始执行字符串。这可能是个问题，如果要搜索的字符串是长的。可能值得创建一个它的字符索引。 IE。前找到可以迭代的匹配项所有目标字符串字符和构建像 'character' -> 这样的映射'它们出现的索引集在字符串'内。这允许执行循环体检查很多如果字符串较长，则速度更快；

一般考虑不存在“最佳算法”，因为“最佳”选择取决于输入数据配置文件和算法使用策略。 IE。如果算法很少执行并且其性能影响微不足道，那么花费大量时间进行优化是没有意义的，最好编写易于维护的简单代码。如果输入字符串相当短，则构建字符索引等没有意义。一般来说，只要有可能，就尽量避免初步优化，如果确实存在瓶颈，则在选择结果算法时仔细考虑所有输入数据。