Cod sursa(job #806102)

Utilizator alexarnautuArnautu Alexandru alexarnautu Data 1 noiembrie 2012 20:25:51
Problema Potrivirea sirurilor Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 kb
#include <cstdio>
#include <vector>
#include <cstring>

using namespace std;

FILE * iFile;
FILE * oFile;

vector<int> sol;
char A[2000010], B[2000010];
int p[2000010], la, lb, n;

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

}

void match()
{
    int q;
    q=0;
    for(int i=1;i<=lb;i++)
    {
        while(q>0&&A[q+1] != B[i])
            q = p[q];
        if(A[q+1] == B[i])
            q++;
        if(q == la)
        {
            n++;
            if(n <= 1000)
                sol.push_back(i-q);
            q=p[q];
        }
    }
}

void read()
{
    fscanf(iFile, "%s", A+1);
    fscanf(iFile, "%s", B+1);
}

void write()
{
    fprintf(oFile, "%d\n", n);
    for(int i=0;i<sol.size();i++)
        fprintf(oFile, "%d ", sol[i]);
}

int main()
{
    iFile = fopen("strmatch.in", "r");
    oFile = fopen("strmatch.out", "w");

    read();
    la=strlen(A+1);
    lb=strlen(B+1);
    prefix();
    match();
    write();

    fclose(iFile);
    fclose(oFile);

    return 0;
}