Cod sursa(job #1364148)

Utilizator gabrielinelusGabriel-Robert Inelus gabrielinelus Data 27 februarie 2015 14:56:48
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.13 kb
#include <cstdio>
#include <cstring>
#include <vector>

#define Nmax 2000050

using namespace std;
char A[Nmax],B[Nmax];
int N,M,total,P[Nmax];
vector<int> sol;

void Read()
{
    scanf("%s%s",A+1,B+1);
    A[0] = '#';
    B[0] = '#';
    N = strlen(A+1);
    M = strlen(B+1);
}

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

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

        P[i] = p;
    }
}

void KMP_Match()
{
    int p = 0;
    for(int i = 1; i <= M; ++i)
    {
        while(p && B[i] != A[p+1])
            p = P[p];
        if(B[i] == A[p+1])
            ++p;
        if(p == N){
            if(total < 1000)
                sol.push_back(i-N);
            ++total;
            p = P[p];
        }
    }
}

void Solve()
{
    KMP_Prefix();
    KMP_Match();
    printf("%d\n",total);
    for(int i = 0; i < sol.size(); ++i)
        printf("%d ",sol[i]);
}

int main()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);

    Read();
    Solve();

    return 0;
}