在字符串中查找子字符串的计数

Question

我必须使用C语言在字符串中找到子字符串的计数.我正在使用该功能,strstr但它只找到第一次出现.

我对算法的想法就像在字符串中搜索strstr而不返回null并在每个循环中对主字符串进行子串.我的问题是如何做到这一点？

Answer 1

你可以做点什么

int count = 0;
const char *tmp = myString;
while(tmp = strstr(tmp, string2find))
{
   count++;
   tmp++;
}

也就是说,当您得到结果时,再次开始在字符串的下一个位置搜索.

strstr()不仅从字符串的开头起作用,而且从任何位置起作用.

Answer 2

应该已经处理过的部分字符串是否应该被消费？

例如,有什么期待答案搜索的情况下oo在foooo,2或3？

• 如果是后者(我们允许子串重叠,答案是三个),那么Joachim Isaksson 建议使用正确的代码.

• 如果我们搜索不同的子串(答案应该是两个),那么请参阅下面的代码(以及此处的在线示例):

  char *str = "This is a simple string";
  char *what = "is";
  
  int what_len = strlen(what);
  int count = 0;
  
  char *where = str;
  
  if (what_len) 
      while ((where = strstr(where, what))) {
          where += what_len;
          count++;
      }
  

Answer 3

使用KMP，您可以在 O(n) 中完成

int fail[LEN+1];
char s[LEN];
void getfail()
{
    //f[i+1]= max({j|s[i-j+1,i]=s[0,j-1],j!=i+1})
    //the correctness can be proved by induction
    for(int i=0,j=fail[0]=-1;s[i];i++)
    {
        while(j>=0&&s[j]!=s[i]) j=fail[j];
        fail[i+1]=++j;
        if (s[i+1]==s[fail[i+1]]) fail[i+1]=fail[fail[i+1]];//optimizing fail[]
    }
}

int kmp(char *t)// String s is pattern and String t is text!
{
    int cnt=0;
    for(int i=0,j=0;t.s[i];i++)
    {
        while(j>=0&&t.s[i]!=s[j]) j=fail[j];
        if (!s[++j])
        {
            j=fail[j];
            cnt++;
        }
    }
    return cnt;// how many times s appeared in t.
}