Cod sursa(job #2175680)

Utilizator MaxTeoTeo Oprescu MaxTeo Data 16 martie 2018 18:25:09
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.84 kb
#include <bits/stdc++.h>
#define NMAX 2000010
using namespace std;

ifstream f("strmatch.in");
ofstream g("strmatch.out");

char A[NMAX],B[NMAX];
int pi[NMAX],ans[1010],a,b,nr;

void prefix()
{
    int q=0;
    for(int i=2;i<=a;++i)
    {
        while(q&&A[q+1]!=A[i])
            q=pi[q];
        if(A[q+1]==A[i])
            ++q;
        pi[i]=q;
    }
}

int main()
{
    f>>A+1; a=strlen(A+1);
    f>>B+1; b=strlen(B+1);

    prefix();

    int q=0;
    for(int i=1;i<=b;++i)
    {
        while(q&&A[q+1]!=B[i])
            q=pi[q];
        if(A[q+1]==B[i])
            ++q;
        if(q==a)
        {
            q=pi[q];
            ++nr;
            if(nr<=1000)
                ans[nr]=i-a;
        }
    }

    g<<nr<<"\n";
    for(int i=1;i<=min(nr,1000);++i)
        g<<ans[i]<<" ";
    return 0;
}