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

Question

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

这是我目前必须做的代码。它工作正常，但我认为可能有更好的方法来做到这一点。在我所做的事情中是否存在任何令人尖叫的低效率或不良做法？有没有像ApacheCommons这样的公共库，我应该加以利用，但我没有

不要担心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)的结果，而不是调用它两次（g1Left = g1DNA.indexOf(window);）

2. 您不必检查所有4个变量是否为==-1，因为您可以同时设置它们

Answer 2

我觉得不错。有人可能会继续在分配方面进行微优化，但这是JIT编译器的工作。如果您觉得算法太慢，请尝试分析它

Answer 3

当前方法

1. 双g1DNA。indexOf（window）调用-第一次调用的结果可以存储并在以后重用
2. 不必要的字符串对象 窗口期间的构造= g0DNA。子串（inx，inx+ 常数。最小匹配）
3. 不必要的gL0，gL1，gR0，gR1 在断言为 关
4. 如果（g0DNA.等于（“”| | g1DNA。等于（“”）检查可以是 改进，以检查 字符串至少有四个符号 每个
5. 最好调用equals（） 关于常数，即使用 “”。等于（arg）。如果arg为null，则可以避免可能的NPE。信息技术 在这里没有太大影响，只是 良好的编码策略
6. 有字符串。isEmpty（）方法 可以用来代替 “”。等于（arg）
7. 未对该对象执行空检查 DNA串

改进

1. 最好是循环最短的 字符串，即您应该检查dna1 和dna2长度，并执行外部 循环对一个较短的 长这样可以最小化 迭代次数
2. 可以避免创建新的字符串对象 并在字符方面进行操作。 此外，您还可以修改 算法，以便与任何 爪哇。lang.CharSequence实现
3. 你会记得无与伦比的 序列，即保留字符集 已检查的序列和 被证明是无与伦比的，以便 最小化外循环时间 迭代。例如，你迭代 在包含多个 “b”chars。检查第二个字符串是否不包含该值 第一次'b'处理期间的字符。 你可以记住这一点，然后停下来 后续的'b'处理 热切地
4. 当您使用字符串时。indexOf（） 搜索从一开始就执行 绳子。如果 要搜索的字符串相当复杂 长的创建一个 它的字符索引。即之前 找到可以迭代的匹配项 所有目标字符串和 构建映射，如“character”->； '它们出现的索引集 在字符串“中。这允许 执行循环体检查 如果是长字符串，则速度更快

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