Cod sursa(job #718120)

Utilizator repp4raduRadu-Andrei Szasz repp4radu Data 20 martie 2012 15:47:45
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.19 kb
#include <fstream>
#include <string.h>
#include <algorithm>


#define MAX 2000050

using namespace std;

char A[MAX], B[MAX];
int pfix[MAX], ap[1024], lF, lS, n;

void citire()
{
    ifstream in("strmatch.in");
    in.getline(A + 1, MAX);
    in.getline(B + 1,MAX);
    A[0] = B[0] = ' ';
    in.close();
}

void getPrefix()
{
    int i, q = 0;
    for(i = 2, pfix[1] = 0; i <= lF; i++)
    {
        while(q && A[q + 1] != A[i])
            q = pfix[q];
        if(A[q + 1] == A[i])
            q++;
        pfix[i] = q;
    }
}

void solve()
{
    lF = strlen(A) - 1, lS = strlen(B) - 1;
    getPrefix();
    int i, q = 0;
    for(i = 1; i <= lS; i++)
    {
        while(q && A[q + 1] != B[i])
            q = pfix[q];
        if(A[q + 1] == B[i])
            q++;
        if(q == lF)
        {
            n++;
            if(n <= 1000)
                ap[n] = i - lF;
            q = pfix[lF];
        }
    }
}

void afisare()
{
    ofstream out("strmatch.out");
    out<<n<<'\n';
    for(int i = 1; i <= min(1000, n); i++)
        out<<ap[i]<<" ";
    out.close();
}

int main()
{
    citire();
    solve();
    afisare();
    return 0;
}