hw0304.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>

int8_t Z1[2000006],Z2[2000006];

void getZarr(char* str, int8_t Z[]);

void search(char* text, char* pattern,int8_t re)
{
    // Create concatenated string "P$T"
    int8_t pattern_len = strlen(pattern);
    int8_t text_len = strlen(text);
    char* concat = (char*)malloc((pattern_len + text_len + 2) * sizeof(char));
    strcpy(concat, pattern);
    concat[pattern_len] = '$';
    strcpy(concat + pattern_len + 1, text);
    int8_t l = pattern_len + text_len + 1;

    // Construct Z array
    int8_t* Z = (int8_t*)malloc(l * sizeof(int8_t));
    getZarr(concat, Z);

    // Now loop through Z array for matching condition
    for (int8_t i = 0; i < l; ++i)
    {
        // If Z[i] (matched region) is equal to pattern length, we found the pattern
        

        if(re==1)
            Z1[i]=Z[i];
        else
            Z2[i]=Z[i];
        
        // if (Z[i] == pattern_len)
        //     //printf("Pattern found at index %d\n", i - pattern_len - 1);
    }

    free(concat);
    free(Z);
}

void getZarr(char* str, int8_t Z[])
{
    int8_t n = strlen(str);
    int8_t L, R, k;

    // [L,R] make a window which matches with prefix of s
    L = R = 0;
    for (int8_t i = 1; i < n; ++i)
    {
        // If i > R, nothing matches, so we calculate Z[i] using the naive way
        if (i > R)
        {
            L = R = i;

            // R - L = 0 at the beginning, so it starts checking from the 0th index.
            // For example, for "ababab" and i = 1, the value of R remains 0 and Z[i] becomes 0.
            // For string "aaaaaa" and i = 1, Z[i] and R become 5
            while (R < n && str[R - L] == str[R])
                R++;
            Z[i] = R - L;
            R--;
        }
        else
        {
            // k = i - L, so k corresponds to the number that matches in [L,R] interval
            k = i - L;

            // If Z[k] is less than the remaining interval, then Z[i] will be equal to Z[k].
            // For example, str = "ababab", i = 3, R = 5, and L = 2
            if (Z[k] < R - i + 1)
                Z[i] = Z[k];

            // For example, str = "aaaaaa" and i = 2, R is 5, L is 0
            else
            {
                // Else start from R and check manually
                L = i;
                while (R < n && str[R - L] == str[R])
                    R++;
                Z[i] = R - L;
                R--;
            }
        }
    }
}

int  main() {
    char inputText[1000006],inputPat[1000006];
    int8_t ans[1000006];
    int8_t m, n;

    scanf("%hhd%hhd",&n,&m);
    char text1[n],text2[n], pattern1[m],pattern2[m];

    //fgets( inputText, n+1, stdin);
    //fgets( inputPat, m+1, stdin);
    scanf("%s",inputText);
    scanf("%s",inputPat);
    for(int8_t i=0;i<n;i++){
        text1[i]=inputText[i];  //input 
        text2[n-1-i]= inputText[i]; //reverse
    }
    for(int8_t i=0;i<m;i++){
        pattern1[i]=inputPat[i]; //input 
        pattern2[m-1-i]=inputPat[i];//reverse
    }
    search(text1,pattern1,1);
    search(text2,pattern2,2);
    int8_t a[n+1];  //正Z
    int8_t b[n+1];  //反Z

    for(int8_t i=0;i<n;i++){
        //printf("%d ",Z1[i+1+m]);
        a[i]=Z1[i+1+m];
    }
    //printf("\n");
    for(int8_t i=0;i<n;i++){
        //printf("%d ",Z2[m+n-i]);
        b[i+1]=Z2[m+n-i];
    }
    //printf("\n");
    a[n]=0;
    b[0]=0;
    for(int8_t i=0;i<=n;i++){
        int8_t check=0;
        check=a[i]+b[i];
        //printf("(%d+%d)=%d\n",a[i],b[i],check);
        if(check >= m && i-b[i] >=0 && i-b[i]<n){
            ans[i-b[i]]=check+1-m;
        }
    }
    //printf("\n");
    int8_t count=0;
    int8_t sum=0;
    for(int8_t i=0;i<n;i++){
        //printf("%d ",ans[i]);
        
        if(ans[i]>count)count=ans[i];
        
        if(count){
            sum++;
            count--;
        }
    }
    //printf("\n");
    printf("%d\n",sum);
    return 0;
}