Count Frequency of a Substring in a String

Question

Given a string T and a pattern P which is also a string. Find the number of occurrences of P in T.

Input

Line 1: contains string P (length is less than or equals to 10^5)

Line 2: contains the string T (length is less than or equals to 10^6)

Output

Write the number of occurrences of P in T

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 5000000
int Count(char T[], char P[])
{
    int count = 0;
    char *pos, *t;
    int index;
    t = &T[0];

    while ((pos = strstr(T, P)) != NULL)
    {
        index = pos - t;
        strcpy(T, T + index + 1);
        count++;
    }
    return count;
}
int main()
{
    char *T = (char *)malloc(N);
    char *P = (char *)malloc(N);
    fgets(P, N, stdin);
    fgets(T, N, stdin);
    if (P[strlen(P) - 1] == '\n')
        P[strlen(P) - 1] = '\0';
    if (T[strlen(T) - 1] == '\n')
        T[strlen(T) - 1] = '\0';
    int count = Count(T, P);
    printf("%d", count);
    return 0;
}

for this input, I get correct output (10) on my laptop but get 9 as output on website.

Pham Q Dung

cdefghijkmlnoPham Q Dungxyz 1234567890Pham Q Dungijkmlnopqrstuvwxyz 1234567890Pham Q Dunghijkmlnopqrstuvwxyz 1234567890Pham Q Dungfghijkmlnopqrstuvwxyz 123456789Pham Q DungefghijkmlnopqrstuvwxyzPham Q DunghijkmlnopqrstuvwxyPham Q Dung67890Pham Q DungbcdefghijkmlnopqrstuvwPham Q Dungqrstuvwxyz 1234567890Pham Q Dung

Are you using some kind of "competition" or "judge" site to learn the basics of C? Your code kind of looks like that. Please note that such sites are *not* any kind of learning or teaching resource to learn basics of anything really. All they tend to teach are bad habits, bad code, and in some cases even *invalid* code. If you're serious about learning programming and C, invest in books and take classes. And once you're comfortable with C, its standard functions, and the common basic algorithms and data-structures, use such sites for leisure, nothing else. — Some programmer dude, May 07 '23 at 16:01
Case in point: `strcpy(T, T + index + 1);` Using a single overlapping string in [`strcpy`](https://en.cppreference.com/w/c/string/byte/strcpy) leads to *undefined behavior*. And allocating 10 *million* bytes for your strings? Why? Does the assignment requirement really say that, or is it just [cargo cult programming](https://en.wikipedia.org/wiki/Cargo_cult_programming)? There's also no error checking, and there are [better way to remove the newline](https://stackoverflow.com/questions/2693776/removing-trailing-newline-character-from-fgets-input) after `fgets`. — Some programmer dude, May 07 '23 at 16:04

Vlad from Moscow · Answer 1 · 2023-05-07T19:14:33.940

This call of strcpy

strcpy(T, T + index + 1);

does not make sense and moreover can invoke undefined behavior.

The source strings shall not be changed within the function,

The function can be declared and defined the following way

size_t Count( const char s1[], const char s2[] )
{
    size_t count = 0;

    size_t n = strlen( s2 );

    for ( const char *p = s1; ( p = strstr( p, s2 ) ) != NULL; p += n ) 
    {
        ++count;
    }

    return count;
}

and called like

size_t count = Count( T, P );
printf( "%zu\n", count );

And do not forget to free the allocated memory

free( P );
free( T );

Count Frequency of a Substring in a String

1 Answers1