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

Answer 1

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 );