trovare il numero di sottostringa nella stringa

Devo trovare il numero di una sottostringa in una stringa utilizzando il linguaggio C.
Sto utilizzando la funzione strstr ma si trova solo la prima occorrenza.

La mia idea dell’algoritmo è qualcosa come la ricerca della stringa, mentre strstr non restituisce null e
per sottostringa della stringa principale in ogni ciclo.
La mia domanda è: come fare?

 

5 Replies
  1. 32

    Si potrebbe fare qualcosa di simile

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

    Che è, quando si ottiene un risultato, avviare la ricerca di nuovo alla successiva posizione della stringa.

    strstr() non funziona solo a partire dall’inizio della stringa, ma da qualsiasi posizione.

    • Se hanno bisogno di essere distinti sottostringhe, si potrebbe prendere in considerazione count+=strlen(string2find)
    • Modifica, ho aggiunto la protezione contro i problemi in caso di string2find=””
    • attenzione loop infinito per “”
    • e i futuri lettori, credo che tu intendessi tmp += strlen(string2find). Nel tuo esempio, si sta aumentando il numero di occorrenze per la lunghezza della stringa!
    • se si stanno trovando “zz” in “zzzz”, avrebbe restituito 3 e (con tmp++) credo che questa è la risposta corretta, se fai una cosa del genere tmp += strlen(string2find) questo sarebbe solo un ritorno con 2.
  2. 5

    Dovrebbe già trattati parti della stringa deve essere consumato o no?

    Per esempio, che aspettano risposta per il caso della ricerca oo in foooo, 2 o 3?

    • Se l’ultimo (si consentire la sottostringa di sovrapposizione, e la risposta è tre), poi Gioacchino Isaksson suggerito del codice di diritto.

    • Se ci ricerca per distinti sottostringhe (la risposta dovrebbe essere due), per poi vedere il codice riportato di seguito (e in linea di esempio qui):

      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

    UTILIZZARE KMP e lo si può fare in un tempo 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.
    }
  4. 2

    I risultati possono essere diversi a seconda se si desidera consentire una sovrapposizione o 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));
    }

    Uscita

    '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);
    }
    • Non usare variabili globali per nessun motivo. void main è sbagliata, dovrebbe essere int main. "%[^\n]s" non fare quello che si vuole; il s non è parte del % direttiva e richiede un letterale s per essere inseriti. Non specificare un limite superiore per gli ingressi; questo è un potenziale di buffer overflow. Controllare sempre il valore di ritorno di scanf se si deve usare. Non utilizzare scanf per l’input dell’utente. strlen restituisce size_t, non int. Si sono ridondanti parentesi nella while condizione; mentre non è un bug di per se, questo disattiva l’avviso di gcc darebbe se si errore di battitura avevo == come =.
    • Il while ciclo non verificare la fine della stringa e può eseguire la fine di str e sub se tutti i caratteri di una partita. j e count sono sempre insieme insieme; sono effettivamente la stessa variabile. L’algoritmo è completamente rotto: non trovare ad esempio "ab" in "aab".
    • In generale, evitare di postare risposte che consistono in un codice unico. Una descrizione dell’algoritmo o una spiegazione di come la vostra risposta è diversa dalle altre, sarebbe di aiuto.

Lascia un commento