[c] kmp 활용 search

예제 코드

#include <stdio>
#include <string>

char str[100005];
char comp[1005];
int pi[1005];

inline bool process()
{
    int i;
    int l , l2 , k;
    
    l = strlen(comp) - 1;
    // Pi 배열 생성 ; O(m)
    
    pi[1] = 0;
    k = 0;
    
    for(i=2; i<=l; i++)
    {
        while(k>0 && comp[k + 1]!=comp[i])
        {
            k = pi[k];
        }
        
        if(comp[k + 1] == comp[i]) k++;
        pi[i] = k;
    }
    // KMP 활용
    l2 = strlen(str) - 1;
    k = 0;
    
    for(i = 1; i <= l2; i++)
    {
        while(k>0 && comp[k + 1]!=str[i])
        {
            k = pi[k];
        }
        
        if(comp[k + 1] == str[i]) k++;
        if(k == l) return 1;
    }
    return 0;
}

int main()
{
    int tn , n , i;
    scanf("%d" , &tn);

    while(tn--)
    {
        scanf("%s" , str + 1);
        str[0] = ' ';
        scanf("%d" , &n);
        
        for(i = 1; i <= n; i++)
        {
            scanf("%s" , comp + 1);
            comp[0] = ' ';
            printf("%c\n" , (process()) ? 'y' : 'n');
        }
    }
    
    return 0;
}