java - 在java中通过搜索和删除旧子字符串来创建子字符串的最快方法是什么？

Question

我的业务逻辑比较奇怪，但总之，我在这里解释一下。 我必须删除第一次或最后一次出现的子字符串，然后重复该过程。我认为下面的代码到目前为止工作正常。现在我想知道如何优化它，因为它对于大输入(字符串长度为 10000)数据表现不佳。

int count =0;
while(s.contains(substr))
{
   s= s.replaceFirst(substr,"");
   // doSomeBusinessLogic(s); 
   count++;    
}
return count;

示例

test 1 
    s = abababab
    substr = ab

    count = 4
test 2 

        s = aeerrb
        substr = er
        count =2 
        because after removing first er, the string becomes aerb,
     so remove the er again. so count is 2.

Edited- as per the answer it looks like matcher is better to use, however, its not producing an excepted answer.

   public class Solution {
        static int maxMoves(String s, String substr) {

            int count = 0;
            StringBuffer buf = new StringBuffer();
            Matcher m = Pattern.compile(substr).matcher(s);
            while (m.find()) {
                m.appendReplacement(buf, "");
                count++;
            }
            m.appendTail(buf);
            // System.out.println(buf.toString());
            return count;

        }

        public static void main(String[] args) {
            System.out.println("Max Moves"+ Solution.maxMoves("aeerrb","er"));

        }



    }

Answer 1

免责声明:此答案中的代码不会处理稍后添加到问题中的示例中给出的测试 2。

使用您的代码，插入打印语句，您将得到:

String s = "This is a test";
String substr = " ";

int count = 0;
while (s.contains(substr)) {
    s = s.replaceFirst(substr, "");
    System.out.println("doSomeBusinessLogic(\"" + s + "\")"); 
    count++;
}
System.out.println("count = " + count);

输出

doSomeBusinessLogic("Thisis a test")
doSomeBusinessLogic("Thisisa test")
doSomeBusinessLogic("Thisisatest")
count = 3

首先，replaceFirst()的参数是一个正则表达式，所以需要对参数进行转义，所以正则表达式特殊字符如.、?, *, [, {, ... 按字面意思处理，而不是作为正则表达式模式。为此，请调用Pattern.quote() .

然后，改进代码，这样您就不会扫描文本两次(contains() 和 replaceFirst())，并从您所在的位置继续扫描，而不是从头开始，使用标准 appendReplacement() 的变体循环:

String s = "This is a test";
String substr = " ";

int count = 0;
StringBuffer buf = new StringBuffer();
Matcher m = Pattern.compile(Pattern.quote(substr)).matcher(s);
while (m.find()) {
    m.appendReplacement(buf, "");
    String ss = buf + s.substring(m.end());
    System.out.println("doSomeBusinessLogic(\"" + ss + "\")"); 
    count++;
}
// not needed here, but loop usually ends with:  m.appendTail(buf);
System.out.println("count = " + count);

输出与之前相同。

<小时/>

作为引用，这里是一个更正常的 appendReplacement 循环，它用 count 值替换空格:

int count = 0;
StringBuffer buf = new StringBuffer();
Matcher m = Pattern.compile(" ").matcher("This is a test");
while (m.find()) {
    m.appendReplacement(buf, String.valueOf(count));
    count++;
}
m.appendTail(buf);
System.out.println(buf.toString()); // prints: This0is1a2test