Cod sursa(job #1331087)

Utilizator aandreiAndrei Stanimir aandrei Data 31 ianuarie 2015 12:24:31
Problema Potrivirea sirurilor Scor 2
Compilator cpp Status done
Runda Arhiva educationala Marime 0.95 kb
#include <iostream>
#include <fstream>
#include <cstdlib>
#include <cstring>

using namespace std;
char a[2000005],b[2000005];
int pi[2000005],pos[1024];
int A,B;
void prefix()
{
    int i,q=0;

    for(i=2,pi[1]=0;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()
{
    ifstream f("strmatch.in");
    ofstream g("strmatch.out");

    int i,q=0,n=0;
    f.getline(a+1,2000000,'\n');
    f.getline(b+1,2000000,'\n');

    A=strlen(a+1);
    B=strlen(b+1);

    prefix();
    for (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[A];
            n++;
            if (n <= 1000)
                pos[n] = i-A;
        }
    }
    g<<q<<endl;
    for(i=1;i<=q&&i<=1000;i++)
        g<<pos[i]<<" ";
}