SPOJ/NHAY.cpp at master · sdssudhu/SPOJ · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
// A Needle in the Haystack

#include <iostream>
using namespace std;

string text,pattern;
int lps[1000001],flag;

void Lps()
{
    int i,j;
    lps[0]=0;
    j=0;
    for(i=1;i<pattern.length();)
    {
        if(pattern[i]==pattern[j])
        {
            ++j;
            lps[i]=j;
            ++i;
        }
        else if(j!=0)
        j=lps[j-1];
        else
        {
            lps[i]=0;
            ++i;
        }
    }
}

void kmp()
{
    Lps();
    int i=0,j=0;
    for(i=0;i<text.length();)
    {
        if(pattern[j]==text[i])
        ++j,++i;
        if(j==pattern.length())
        {
            cout<<i-j<<endl;
            flag=1;
            j=lps[j-1];
        }
        else if(i<text.length() && pattern[j]!=text[i])
        {
             if (j != 0)
                j=lps[j-1];
            else
                i=i+1;
        }
    }
}


int main()
{
    int m;
    while(cin>>m)
    {
        flag=0;
    cin>>pattern>>text;
    kmp();
    if(flag==0)
    cout<<endl;
    }
	return 0;
}