SPOJ – NAJPF – Pattern Find

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

vector<ll>pi;
void preFunc(string s)
{
    ll len=(ll)s.size();
    pi.resize(len+5);
    pi[0]=0;
    for(ll i=1;i<len;i++){
        ll j=pi[i-1];
        while((j>0)&&(s[i]!=s[j]))j=pi[j-1];
        if(s[i]==s[j])j++;
        pi[i]=j;
    }
}

int main()
{
    ll t;
    cin>>t;
    ll ck=0;
    while(t--){
        string s,p;
        cin>>s>>p;
        ll lenp=p.size();
        p+="#";
        p+=s;
        ll len=p.size();
        preFunc(p);
        vector<ll>ans;
        for(ll i=lenp;i<len;i++){
            if(pi[i]==lenp)ans.push_back(i-lenp-lenp+1);
        }
        ll ct=ans.size();
        if(ck==0)ck++;
        else cout<<"\n";
        if(ct==0)cout<<"Not Found\n";
        else{
            cout<<ct<<"\n";
            ll ck1=0;
            for(ll i=0;i<ct;i++){
                if(ck1==0)ck1++;
                else  cout<<" ";
                cout<<ans[i];
            }
            cout<<"\n";
        }
    }
    return 0;
}

Code language: PHP (php)