Cod sursa(job #2071640)

Utilizator smashsmash everything smash Data 20 noiembrie 2017 20:47:52
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#include <fstream>
#include<cstring>
using namespace std;

ifstream cin ("strmatch.in");
ofstream cout ("strmatch.out");

char s[2000000],p[2000000];
int n,m,pi[2000000],sol[2000000],nr;

void construct ()
{
    int k; pi[0]=-1;
    for(int i=1;i<=m;i++)
    {
        k=pi[i-1];
        while(k>-1 && p[i]!=p[k+1]) k=pi[k];
        if(p[i]==p[k+1]) ++k;
        pi[i]=k;
    }
}

void solve ()
{
    int k;
    for(int i=0;i<=n;i++)
    {
       if(i>0) k=sol[i-1]; else k=-1;
       while(k>-1 && s[i]!=p[k+1]) k=pi[k];
       if(s[i]==p[k+1]) k++;
       sol[i]=k;
       if(k==m) nr++;
    }
}

void read ()
{
    cin>>p>>s;
    n=strlen(s)-1;
    m=strlen(p)-1;
}

void write ()
{ int y=0;
    cout<<nr<<"\n";
    for(int i=0;i<=n;i++)
    {
        if(sol[i]==m) cout<<i-m<<" ",y++;
        if(y==1000) break;
    }
}

int main()
{
    read();
    construct();
    solve();
    write();
    cin.close();
    cout.close();
    return 0;
}