Cod sursa(job #2287891)

Utilizator FunnyStockyMihnea Andreescu FunnyStocky Data 22 noiembrie 2018 17:14:57
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.38 kb
#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;

const int N=2000000+5;

string pat,s;
int m,n;
int ps[N];
vector<int>ans;

inline void LP()
{
    ps[0]=0;
    int i=1,cur=0;
    while(i<m)
    {
        if(pat[i]==pat[cur])
        {
            cur++;
            ps[i]=cur;
            i++;
        }
        else
        {
            if(cur==0)
            {
                i++;
            }
            else
            {
                cur=ps[cur-1];
            }
        }
    }
}

inline void KMP()
{
    int i=0;
    int j=0;
    while(i<n)
    {
        if(s[i]==pat[j])
        {
            j++;
            i++;
        }
        if(j==m)
        {
            ans.push_back(i-m);
            j=ps[j-1];
        }
        if(i<n && s[i]!=pat[j])
        {
            if(j==0)
            {
                i++;
            }
            else
            {
                j=ps[j-1];
            }
        }
    }
}

int main()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    cin>>pat>>s;
    m=pat.size();
    n=s.size();
    LP();
    KMP();
    cout<<ans.size()<<"\n";
    if(ans.size()>1000)
    {
        ans.resize(1000);
    }
    for(auto &x:ans)
    {
        cout<<x<<" ";
    }
    cout<<"\n";
    return 0;
}
/**


**/