Cod sursa(job #1107434)

Utilizator gabrielvGabriel Vanca gabrielv Data 13 februarie 2014 21:31:59
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.17 kb
#include <cstdio>
#include <cstring>
#include <vector>

using namespace std;

#define NMAX 2000015

char A[NMAX],B[NMAX];

int P[NMAX];

int N, M;

int Antwort;

vector < int > Sol;

void Scannen()
{
    freopen("strmatch.in","r",stdin);

    fgets(A+1,NMAX - 3,stdin);
    fgets(B+1,NMAX - 3,stdin);

    N = strlen(A+1)-1;
    M = strlen(B+1)-1;
}

void Losen()
{
    int q = 0;
    for(int i=2;i<=N;i++)
    {
        while(q && A[q+1] != A[i])
            q = P[q];

        if(A[q+1] == A[i])
            q++;

        P[i] = q;
    }

    q = 0;
    for(int i=1;i<=M;i++)
    {
        while(q && A[q+1] != B[i])
            q = P[q];

        if(A[q+1] == B[i])
            q++;

        if(q == N)
        {
            q = P[N];

            ++Antwort;

            if(Antwort <= 1000)
                Sol.push_back(i-N);
        }
    }
}

void Drucken()
{
    freopen("strmatch.out","w",stdout);

    printf("%d\n",Antwort);

    for(vector < int > ::iterator it = Sol.begin(); it != Sol.end(); ++ it)
        printf("%d ",*it);
}

int main()
{
    Scannen();
    Losen();
    Drucken();
    return 0;
}