Cod sursa(job #1105344)

Utilizator cristitamasTamas Cristian cristitamas Data 11 februarie 2014 18:53:25
Problema Potrivirea sirurilor Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.04 kb
#include <iostream>
#include <cstdio>
#include <cstring>
#define Nmax 2000010
using namespace std;

char A[Nmax],B[Nmax];
int LgA,LgB;
int P[Nmax];
int Sol[1005];
int N;

void Prefix()
{
    int q=0;
    for(int i=2;i<=LgA;++i)
    {
        while(q && A[q+1]!=A[i])
            q=P[i];
        if(A[q+1]==A[i])
            ++q;
        P[i]=q;
    }
}

void PrefixB()
{
    int q=0;
    for(int i=1;i<=LgB;++i)
    {
        while(q && A[q+1]!=B[i])
            q=P[i];
        if(A[q+1]==B[i])
            q++;
        if(q==LgA)
        {
            q=P[LgA];
            if(N<=1000)
                Sol[N++]=i-LgA;
            else
                break;
        }
    }
}


int main()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    scanf("%s\n",A+1);
    scanf("%s\n",B+1);
    A[0]=B[0]='0';
    LgA=strlen(A)-1;
    LgB=strlen(B)-1;
    Prefix();
    PrefixB();
    printf("%d\n",N);
    for(int i=0;i<N;++i)
        printf("%d ",Sol[i]);
    return 0;
}