trouver le nombre de sous-chaîne dans la chaîne

Je dois trouver le comptage d'une sous-chaîne dans une chaîne de caractères en utilisant le langage C.
Je suis l'aide de la fonction strstr mais il ne trouve que la première occurrence.

Mon idée de l'algorithme est quelque chose comme la recherche dans la chaîne alors que strstr ne retourne pas null et
pour la sous-chaîne de la chaîne principale sur chaque boucle.
Ma question est comment le faire?

source d'informationauteur Jordan Borisov

  1. 24

    Vous pourriez faire quelque chose comme

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

    Qui est, quand vous obtenez un résultat, commencer à chercher de nouveau à la prochaine position de la chaîne.

    strstr() ne fonctionne pas qu'à partir du début d'une chaîne, mais à partir de n'importe quelle position.

  2. 5

    Devrait déjà traitées les pièces de la chaîne doit être consommé ou pas?

    Par exemple, à quoi s'attendre de réponse pour le cas de la recherche oo dans foooo2 ou 3?

    • Si ce dernier (nous permettre de sous-chaîne qui se chevauchentet la réponse est de trois), puis Joachim Isaksson suggéré le bon code.

    • Si nous recherche de sous-chaînes distinctes (la réponse doit être deux), puis voir le code ci-dessous (et en ligne exemple ici):

      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++;
    }
  3. 4

    UTILISATION KMP et vous pouvez le faire en 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.
}

    Vous pouvez voir les pages du wiki pour plus de détails

  4. 2

    Les résultats peuvent être différents selon si vous permettre un chevauchement ou non:

    //gcc -std=c99
#include <stdbool.h>
#include <stdio.h>
#include <string.h>

static int
count_substr(const char *str, const char* substr, bool overlap) {
  if (strlen(substr) == 0) return -1; //forbid empty substr

  int count = 0;
  int increment = overlap ? 1 : strlen(substr);
  for (char* s = (char*)str; (s = strstr(s, substr)); s += increment)
    ++count;
  return count;
}

int main() {
  char *substrs[] = {"a", "aa", "aaa", "b", "", NULL };
  for (char** s = substrs; *s != NULL; ++s)
    printf("'%s' ->  %d, no overlap: %d\n", *s, count_substr("aaaaa", *s, true),
       count_substr("aaaaa", *s, false));
}

    Sortie

    'a' ->  5, no overlap: 5
'aa' ->  4, no overlap: 2
'aaa' ->  3, no overlap: 1
'b' ->  0, no overlap: 0
'' ->  -1, no overlap: -1
  5. -3
    /* 
 * C Program To Count the Occurence of a Substring in String 
 */
#include <stdio.h>
#include <string.h>

char str[100], sub[100];
int count = 0, count1 = 0;

void main()
{
    int i, j, l, l1, l2;

    printf("\nEnter a string : ");
    scanf("%[^\n]s", str);

    l1 = strlen(str);

    printf("\nEnter a substring : ");
    scanf(" %[^\n]s", sub);

    l2 = strlen(sub);

    for (i = 0; i < l1;)
    {
        j = 0;
        count = 0;
        while ((str[i] == sub[j]))
        {
            count++;
            i++;
            j++;
        }
        if (count == l2)
        {
            count1++;                                   
            count = 0;
        }
        else
            i++;
    }    
    printf("%s occurs %d times in %s", sub, count1, str);
}