Mintruth

#include <stdio.h>
#include <string.h>
#define sz 100000
int max(int a,int b){
    return (a>b)?a:b;
}
int pi[sz];
char s[sz], buff[sz], ans[sz];
int find(int m, int n, int l){
    memset(pi,0,sizeof(int)*m);
    for(int i=1; i<m; ++i){
        int k=pi[i-1];
        while(k>0 && buff[i]!=buff[k])
            k=pi[k-1];
        if(buff[k]==buff[i])
            ++k;
        pi[i]=k;
     }
     int k=0, pos=-1;
        if(s[0]==buff[0]){
            ++k;
           if(m==1)
               return l;
      }
        for(int i=1; i<n; ++i){
            if (k==m)
                k=pi[k-1];
            while (k>0 && buff[k]!=s[i])
                k=pi[k-1];
            if(buff[k]==s[i])
                ++k;
            if (k==m && i-m+1>=l)
                return i-m+1;
        }
        return -1;

}
int main(){

    char c=getchar();
    int n=0;
    while(c!='\n'){
        s[n]=c;
        ++n;
        c=getchar();
    }
    memcpy(ans,s,n);
    c=getchar();
    int left=0;
    while(true){
         while(c==' ')
             c=getchar();
        int m=0;
         while (c!='\n'&&c!=' '){
            buff[m]=c;
            ++m;
            c=getchar();
        }
        if(m==0)
            break ;
        int pos=find(m,n,left);
        if (pos==-1){
            puts("I HAVE FAILED!!!");
            return 0;
        }
        for(int i=max(left-1,0);i<pos;++i)
             if(s[i]!=' ')
                  ans[i]='_';
        left=pos+m+1;
    }
    if(left>0)
        for(int i=left-1;i<n;++i)
            if(s[i]!=' ')
                ans[i]='_';
    for(int i=0; i<n; ++i)
       putchar(ans[i]);
    return 0;
}