Spoj NHAY Solution

#include<bits/stdc++.h>

using namespace std;

vector<int> arrayvalue(string ch)

{

    int i, j, l = ch.size();

    vector<int>lps(l);

    int index = 0;

    for(i=1; i<l; )

    {

        if(ch[i] == ch[index])

        {

            lps[i] = index + 1;

            i++;

            index++;

        }

        else

        {

            if(index != 0)

                index = lps[index - 1];

            else

            {

                lps[i] = index;

                i++;

            }

        }

    }

    return lps;

}

void kmp(string ch, string an)

{

    int i, j, l = an.size();

    bool ans = false;

    int t, d = 1;

    vector<int>lps = arrayvalue(an);

    i = j = 0;

    while(i<ch.size())

    {

        if(ch[i] == an[j])

        {

            i++;

            j++;

        }

        else

        {

            if(j != 0)

            {

                j = lps[j-1];

            }

            else

                i++;

        }

        if(j == l)

        {

            j = 0;

            t = i - l;

            cout << t << endl;

            i = t+1;

            ans = true;

        }

    }

    if(ans == false)

        cout << endl;

}

int main()

{

    string a, b;

    int n, d = 1;

    while(cin >> n >> a >> b)

    {

        if(a.size() > b.size())

        {

            cout << endl << endl;

            return 0;

        }

        kmp(b, a);

        if(d > 1)

            cout << endl;

        d++;

    }

    return 0;

}