NHAY Doubt

[aryan_0406]

SPOJ.com - Problem NHAY

#include<bits/stdc++.h>
using namespace std;
void child(int*,string);
void parent(int*,string,string);
int main()
{
    int i,j,k,length;
    string needle,haystack,temp1,temp2;
    while(cin>>length)
    {
        needle+='0';
        haystack+='0';
        cin>>temp1>>temp2;
        needle+=temp1;
        haystack+=temp2;
        if(needle.length()>haystack.length()){
            cout<<endl;
            needle.clear();
            haystack.clear();
            continue;
        }
        int lps[needle.length()];
        child(lps,needle);
        parent(lps,needle,haystack);
        needle.clear();
        haystack.clear();
        cout<<endl;
    }
    return 0;
}
void child(int lps[],string needle)
{
    int i=2,j,len=0;
    lps[1]=0;
    while(i<needle.length())
    {
        if(needle[i]==needle[len+1])
        {
            len++;
            lps[i++]=len;
        }
        else
        {
            if(len!=0)
            {
                len=lps[len];
            }
            else{
                lps[i++]=0;
            }
        }
    }
}
void parent(int lps[],string needle,string haystack)
{
    int i=1,len=0;
    while(i<=haystack.length()){
            //cout<<i<<" "<<len+1<<endl;
            if(len==needle.length()-1){
                cout<<i-len-1<<endl;
                len=lps[len];
            }
            if(i>=haystack.length())
                break;
        if(haystack[i]==needle[len+1]){
            len++;
            i++;
        }
        else{
            if(len!=0){
                len=lps[len];
            }
            if(len==0){
                i++;
            }
        }
    }
}

Can someone help me in finding out why it is not getting accepted, What changes should i make to correct this code?

[aryan_0406]

Some hint would be appriciated.

[simes]

What algorithm is this?

needle+=‘0’;
haystack+=‘0’;

This looks odd - how will it affect the search if the strings contain zeros?

[aryan_0406]

Actually this i have done this so that my string length starts from number 1 and i have made the code according to that.
Is it giving wrong answer for any test case?

[simes]

Something is, because you’re getting WA, but I haven’t found any.

Wouldn’t it be cleaner to just output i+1 when reporting the matching positions? (or just remove the -1 that’s already there.)

What algorithm is this?

[aryan_0406]

This is Knuth-Morris_pratt(KMP) algorithm.

[simes]

It was the names of the methods that threw me, Parent & Child.

[aryan_0406]

child is for calculating lps length of needle and parent to matching string of needle and haystack.

[aryan_0406]

I want to know whether i have given proper spaces or not. It is not clearly given in question actually.
“Note the double empty line in the output, which means that no match was found for the second test case.” Is this the reason why i am getting wrong answer?

[simes]

It’s always best to match the given output format exactly. That said, many problems will be using the standard judge that ignores white space. The trouble is, you can never be certain whether white space is important or not until after you’ve got accepted.

I just modified my AC code to not write the blank line after each test case, and it still got AC - so I think white space isn’t important here.

[simes]

I don’t know whether there are any test cases like this, but try these:

2
a_
banana_man
2
_m
banana_man

where _ represents a space.