#include <iostream>
#include<fstream>
#include <cstring>
using namespace std;
short int flag;
void preKMP(string pattern, int f[])
{
    int m = pattern.length(), k;
    f[0] = -1;
    for (int i = 1; i < m; i++)
    {
        k = f[i - 1];
        while (k >= 0)
        {
            if (pattern[k] == pattern[i - 1])
                break;
            else
                k = f[k];
        }
        f[i] = k + 1;
        cout<<f[i];
    }
    cout<<"\n"<<"\n";
}

//check whether target string contains pattern
bool KMP(string pattern, string target)
{
    int m = pattern.length();
    int n = target.length();
    int f[m];
    preKMP(pattern, f);
    int i = 0;
    int k = 0;
    while (i < n)
    {
        if (k == -1)
        {
            i++;
            k = 0;
        }
        else if (target[i] == pattern[k])
        {
            i++;
            k++;
            if (k == m)
            {
                flag=k;
                return 1;
            }
        }
        else
            k = f[k];
    }
    return 0;
}

int main()
{
    ifstream fin("kmp.in");
    string tar;
    string pat;
    fin>>pat>>tar;
    if (KMP(pat, tar))
        {
                for(short int j=1;j<=pat.length();j++){
                                                            tar[flag-j]=toupper(tar[flag-j]);
                                                      }
            cout<<"'"<<pat<<"' found in string '"<<tar<<"'"<<endl;
        }
    else
        cout<<"'"<<pat<<"' not found in string '"<<tar<<"'"<<endl;
        cout<<flag<<"\n";
        system("PAUSE");
    return 0;
}