Cod sursa(job #1808801)

Utilizator vladbatalanBatalan Vlad vladbatalan Data 18 noiembrie 2016 09:50:54
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.3 kb
#include <fstream>
#include <cstring>

using namespace std;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

char A[2000010], B[2000010];
int q, prefix[2000010],LGa,LGb;
int n, poz[1024];

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

int main()
{
    fin>>A>>B;
    q=0;
    LGa=0;
    for(; (A[LGa] >= 'A' && A[LGa] <= 'Z') || (A[LGa] >= 'a' && A[LGa] <= 'z')
            || (A[LGa] >= '0' && A[LGa] <= '9'); ++LGa);
    for(; (B[LGb] >= 'A' && B[LGb] <= 'Z') || (B[LGb] >= 'a' && B[LGb] <= 'z')
            || (B[LGb] >= '0' && B[LGb] <= '9'); ++LGb);
    for(int i=LGa; i>0; i--)A[i]=A[i-1];
    A[0]='#';
    for(int i=LGb; i>0; i--)B[i]=B[i-1];
    B[0]='#';
    make_prefix();

    q=0;
    n=0;
    for(int i=1; i<=LGb; i++)
    {
        while(q>0 && A[q+1]!=B[i])
            q=prefix[q];
        if(A[q+1]==B[i])
            q++;
        if(q==LGa)
        {
            q=prefix[LGa];
            if(n<1000)
                poz[++n]=i-LGa;
        }
    }
    fout<<n<<'\n';

    for(int i=1; i<=n; i++)
    {
        fout<<poz[i];
        if(i!=n)
            fout<<' ';
    }
    return 0;
}