在字符串中找到子字符串的出现次数

Question

为什么下面的算法对我来说没有停止？

在下面的代码中，str是我要搜索的字符串，而findStr是我试图找到其出现次数的字符串。

String str = "helloslkhellodjladfjhello";
String findStr = "hello";
int lastIndex = 0;
int count = 0;
    
while (lastIndex != -1) {
    lastIndex = str.indexOf(findStr,lastIndex);
    
    if( lastIndex != -1)
        count++;
           
    lastIndex += findStr.length();
}

System.out.println(count);

- bobcom

---

我们在Udacity中做了一件非常好的事情：我们使用了newSTR = str.replace(findStr, "")；并返回count = ((str.length() - newSTR.length())/findStr.length())。 - SolarLunix

类似的字符问题：https://dev59.com/n3VC5IYBdhLWcg3wfxM8 - koppor

难道你不想考虑搜索字符串的前缀和后缀相同的情况吗？在这种情况下，我认为没有任何建议的答案会起作用。这里有一个例子。在这种情况下，您需要更复杂的算法，例如Knuth Morris Pratt（KMP），该算法已编码在CLRS书中。 - Sid

它对你来说不会停止，因为在达到你的“停止”条件（lastIndex == -1）之后，你通过增加lastIndex的值（lastIndex += findStr.length();）将其重置。 - Legna

@Sid 如果你想要那种行为，你可以每次只将 lastIndex 增加 1 而不是 findStr.length。例如在我的情况下，我只需要知道一个字符是否匹配，不关心多个重叠的计数。所以这取决于每个人的使用情况。 - Adam Burley

请查看：https://www.geeksforgeeks.org/frequency-substring-string/ - modos

Answer 1

使用Apache Commons Lang中的StringUtils.countMatches如何？

String str = "helloslkhellodjladfjhello";
String findStr = "hello";

System.out.println(StringUtils.countMatches(str, findStr));

那会输出：

3

- A_M

---

无论这个建议多么正确，它都不能作为解决方案被接受，因为它没有回答原帖作者的问题。 - kommradHomer

这个是否已经被弃用了？我的IDE没有识别出来。 - Vamsi Pavan Mahesh

@VamsiPavanMahesh StringUtils是Apache Commons的一个库。在这里查看：https://commons.apache.org/proper/commons-lang/javadocs/api-2.6/org/apache/commons/lang/StringUtils.html - Anup

这个答案是 Peter Lawrey 一天前的回答的复制（请参见下面）。 - Zon

StringUtils 没有 countMatches 方法。 - plaidshirt

自StringUtils 3版本以来，org.apache.commons.lang3.StringUtils已经存在。 - pikimota

Answer 2

您的lastIndex += findStr.length();语句放在了括号外面，导致无限循环（当未找到匹配项时，lastIndex始终等于findStr.length()）。

这里是修复后的版本：

String str = "helloslkhellodjladfjhello";
String findStr = "hello";
int lastIndex = 0;
int count = 0;

while (lastIndex != -1) {

    lastIndex = str.indexOf(findStr, lastIndex);

    if (lastIndex != -1) {
        count++;
        lastIndex += findStr.length();
    }
}
System.out.println(count);

- Olivier

---

这对于字符串"aaa"和子串"aa"将会失败。它将返回1，而计数是两个。出现的索引是[0,1]。 - Niko

@Niko 正确的结果取决于是否允许重叠匹配。 - Unmitigated

Answer 3

一个更短的版本。 ;)

String str = "helloslkhellodjladfjhello";
String findStr = "hello";
System.out.println(str.split(findStr, -1).length-1);

- Peter Lawrey

---

return haystack.split(Pattern.quote(needle), -1).length - 1; 如果 needle=":)"意思是，将 haystack 字符串按照 needle 字符串进行分割，然后返回分割出来的子字符串个数减 1。其中 needle=":)" 是一个例子。 - Mr_and_Mrs_D

@lOranger 如果没有,-1，它将会删除尾部匹配。 - Peter Lawrey

哎呀，谢谢，这真是个好消息！这会教会我去读javdoc中的小字...... - Laurent Grégoire

不错！但是它只包括不重叠的匹配，对吗？比如，在“aaa”中匹配“aa”，将返回1而不是2？当然，包括重叠或非重叠的匹配都是有效的，并且取决于用户的要求（也许可以添加一个标志来指示是否计算重叠，是/否）？ - Cornel Masson

请尝试将此代码在 "aaaa" 和 "aa" 上运行，正确答案是 3 而不是 2。 - Kalyanaraman Santhanam

Answer 4

最后一行代码会引起问题。lastIndex永远不可能是-1，因此会产生无限循环。将最后一行代码移到if块中可以解决此问题。

String str = "helloslkhellodjladfjhello";
String findStr = "hello";
int lastIndex = 0;
int count = 0;

while(lastIndex != -1){

    lastIndex = str.indexOf(findStr,lastIndex);

    if(lastIndex != -1){
        count ++;
        lastIndex += findStr.length();
    }
}
System.out.println(count);

- codebreach

---

这个回复是我一个小时之前发布的帖子的完全复制;) - Olivier

请注意，这个代码可能会返回预期的结果，也可能不会。对于子字符串 "aa" 和要搜索的字符串 "aaa"，期望出现次数可能是一个（由此代码返回），但也可能是两个（在这种情况下，您需要使用 "lastIndex++" 而不是 "lastIndex += findStr.length()"），这取决于您要查找的内容。 - Stanislav Kniazev

@Olivier 没看到那个... :(@Stan 完全正确... 我只是在修复问题中的代码... 猜想这取决于 Bobcom 在字符串中所指的出现次数的含义... - codebreach

人们什么时候才会学会将这样的东西封装在复制粘贴的静态方法中？请看下面我的答案，它也更加优化。 - mjs

这里的寓意是，如果你想要写一个答案，请先检查是否已经有人写了完全相同的答案。无论你的答案是复制的还是独立撰写的，重复出现同样的答案其实没有任何好处。请确保内容准确无误、通俗易懂。 - Dawood ibn Kareem

Answer 5

你真的需要自己处理匹配吗？特别是如果你只需要出现次数，正则表达式会更整洁：

String str = "helloslkhellodjladfjhello";
Pattern p = Pattern.compile("hello");
Matcher m = p.matcher(str);
int count = 0;
while (m.find()){
    count +=1;
}
System.out.println(count);     

- Jean

---

这段代码无法找到特殊字符，对于下面的字符串将会返回0：String str = "hel+loslkhel+lodjladfjhel+lo"; Pattern p = Pattern.compile("hel+lo"); - Ben

如果你正确表达你的正则表达式，它将起作用。尝试使用Pattern.compile("hel\\+lo");。在正则表达式中，+符号有特殊含义，需要进行转义。 - Jean

如果您想要将任意字符串作为精确匹配项，并忽略所有特殊的正则表达式字符，那么 Pattern.quote(str) 是您的好帮手！ - Mike Furtak

当str = "aaaaaa"时，这个不适用于"aaa"。有4个答案，但你的只给出了2个。 - Pujan

这个解决方案对于这种情况不起作用：str =“This is a test \n\r string”，subStr =“\ r”，它显示0次出现。 - Maksym Ovsianikov

现代的Java（如1.8）能否通过一些巧妙的迭代器来减少代码行数？ - Phlip

Answer 6

我很惊讶没有人提到这个一行代码的解决方案。它简单、简洁，并且比str.split(target, -1).length-1稍微快一点。

public static int count(String str, String target) {
    return (str.length() - str.replace(target, "").length()) / target.length();
}

- kmecpp

---

应该是最佳答案。谢谢！ - lakam99

完美的回答！！ - Krishna

请注意：如果目标字符串为空，则会抛出ArithmeticException异常，因为除以零。 - Attila

当然会抛出 NullPointerException，如果 str 或 target 为空。计算空字符串的意义是什么？ - syme

Answer 7

这里有一个漂亮且可重复使用的方法：

public static int count(String text, String find) {
        int index = 0, count = 0, length = find.length();
        while( (index = text.indexOf(find, index)) != -1 ) {                
                index += length; count++;
        }
        return count;
}

- mjs

---

非常慢。这基本上就是我正在使用的，而且它超级慢。我正在寻找一些快速的东西。 - FractalBob

它为什么这么慢？几乎没有比这更优化的可能了。你一定是用了烂电脑。 - mjs

戴尔XPS 13 9370。 - FractalBob

Answer 8

String str = "helloslkhellodjladfjhello";
String findStr = "hello";
int lastIndex = 0;
int count = 0;

while((lastIndex = str.indexOf(findStr, lastIndex)) != -1) {
     count++;
     lastIndex += findStr.length() - 1;
}
System.out.println(count);

循环结束时计数器为3；希望这能帮到你。

- dfa

---

代码存在错误。如果我们搜索单个字符，findStr.length() - 1 的结果为0，则会陷入无限循环。 - Jan Bodnar

Answer 9

public int countOfOccurrences(String str, String subStr) {
  return (str.length() - str.replaceAll(Pattern.quote(subStr), "").length()) / subStr.length();
}

- Maksym Ovsianikov

---

好的回答。您能否添加一些关于它如何工作的注释？ - santhosh kumar

当然，str - 是我们的源字符串，subStr - 是子字符串。目标是计算 subStr 在 str 中出现的次数。为此，我们使用公式：(a-b)/c，其中 a - str 的长度，b - 在 str 中除去所有 subStr 的长度（为此，我们从 str 中删除所有 subStr），c - subStr 的长度。因此，基本上我们从 str 的长度中提取 - 去掉所有 subStr 的 str 的长度，然后将结果除以 subStr 的长度。如果您有任何其他问题，请告诉我。 - Maksym Ovsianikov

Santhosh，欢迎您！重要的是要在subStr中使用Pattern.quote，否则在某些情况下可能会失败，例如：str =“This is a test \n\r string”，subStr =“\r”。这里提供的一些类似答案没有使用Pattern，因此在这种情况下它们将失败。 - Maksym Ovsianikov

没有必要使用正则表达式，应该使用replace而不是replaceAll。 - NateS

Answer 10

很多给出的答案在以下一个或多个方面失败：

• 任意长度的模式
• 重叠匹配（例如在“23232”中计数“232”或在“aaa”中计数“aa”）
• 正则表达式元字符

下面是我写的代码：

static int countMatches(Pattern pattern, String string)
{
    Matcher matcher = pattern.matcher(string);

    int count = 0;
    int pos = 0;
    while (matcher.find(pos))
    {
        count++;
        pos = matcher.start() + 1;
    }

    return count;
}

示例调用:

Pattern pattern = Pattern.compile("232");
int count = countMatches(pattern, "23232"); // Returns 2

如果您想进行非正则表达式搜索，只需使用 LITERAL 标志适当编译您的模式即可：

Pattern pattern = Pattern.compile("1+1", Pattern.LITERAL);
int count = countMatches(pattern, "1+1+1"); // Returns 2

- benkc

---

是的...很惊讶Apache StringUtils中没有类似的东西。 - mike rodent

最佳答案是它可以处理重叠模式。 - Ravi K M