Cod sursa(job #1123460)

Utilizator cristitamasTamas Cristian cristitamas Data 26 februarie 2014 08:34:41
Problema Potrivirea sirurilor Scor 78
Compilator cpp Status done
Runda Arhiva educationala Marime 1.08 kb
#include <iostream>
#include <cstdio>
#include <cstring>
#define Min(x,y) (x<y?x:y)
#define Nmax 2000010
using namespace std;

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

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

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



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