kmp.c

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

int* longestPrefixSufix(char* s);

int main(void) {
    int N;
    scanf("%d", &N);
    for(int n = 0; n < N; n++){
        char s[100000];
        char p[100000];
        scanf("%s", s);
        scanf("%s", p);
        printf("%d\n",kmp(s,p));
    }
    return 0;
}

int kmp(char* s, char* p){
    int* t = longestPrefixSufix(s);
    int i=0;
    int j=0;
    int ls=strlen(s);
    int lp=strlen(p);
    while(i<ls){
        if(s[i]==p[j]){
            if(j==lp-1){
                return i-j;
            }else{
                i++;
                j++;
            }
        }else{
            if(j>0){
                j=t[j-1];
            }else{
                i++;
            }
        }
    }
    return -1;
}

int* longestPrefixSufix(char* s){
    int *t;
    t = malloc(sizeof(int)*strlen(s));
    int i=1;
    int j=0;
    t[0]=0;
    while(i<strlen(s)){
        if(s[i]==s[j]){
            t[i]=j+1;
            i++;
            j++;
        }else if(j>0){
            j=t[j-1];
        }else{
            t[i]=0;
            i++;
        }
    }
    return t;
}