int F[MAX];

void preKMP (char* pattern, int m){
    F[0]=F[1]=0;

    for (int i=2; i<=m; ++i){
        // j - индекс прошлого совпадения с префиксом
        int j=F[i-1];

        for (;;){
            // если данный символ i-1 расширяет данное совпадение j, то устанавливаем соответствующее значение в F[i-1]
            if(pattern[j]==pattern[i-1]){
                 F[i]=j+1;
                 break;
            }

            // если дошли до пустой строки
            if(j==0){
                 F[i]=0;
                 break;
            }
            
            // переходим к следующему совпадению
            j=F[j];
        }
    }
}

// возвращает индекс, с которого начинается первое полное совпадение

int KMP (char* pattern, int m, char* text, int n){
    preKMP(pattern, m);
    
    int j=0; // начальная позиция в подстроке
    int i=0; // начальная позиция в строке

    for (;;){
         // достигнут конец строки?
         if (i==n)
              break;
         
         // если данные символы строки и искомого образца совпадают....
         if (text[i]==pattern[j]){
              j++; // переходим к следующему символу образца
              i++; // и следующему символу строки
              if(j==m){ // нашли!
                   return i-m;
              }
         } else if(j>0){ // если можно перейти к другому префиксу, перейдем
              j=F[j];
         }
         else // если нельзя, переходим к следующему символу строки
             i++;
    }
    
    return -1;
}