Cod sursa(job #2063209)

Utilizator patricia.predaPatricia Preda patricia.preda Data 11 noiembrie 2017 10:12:53
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.12 kb
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#define Lg 2000000
#define minim(a,b) ((a<b)? a:b)

using namespace std;
vector <int> sol;
char a[Lg],b[Lg];
int vect[Lg],n,m,pos[1024],l;

void prefix()
{
    int j=0;
    //vect[1]=1;
    for(int i=2;i<=n;i++)
    {
        while(j && a[j+1]!=a[i])
            j=vect[j];
        if(a[j+1]==a[i])
            j++;
        vect[i]=j;
    }
}

void parcurgere()
{
    int j=0;
    for(int i=1;i<=m;i++)
    {
        while(j && a[j+1]!=b[i])
            j=vect[j];
        if(a[j+1]==b[i])
            j++;
        if(j==n)
        {
            j=vect[n];
            if((l+1)<=1000)
                pos[++l]=i-n;
        }
    }
}
void afisare()
{
    printf("%d\n", l);
    for(int i=1;i<=minim(l,1000);i++)
        printf("%d ", pos[i]);
    printf("\n");
}

int main()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    fgets(a+1,Lg,stdin);
    fgets(b+1,Lg,stdin);
    n=strlen(a+1)-1;
    m=strlen(b+1)-1;
    prefix();
    parcurgere();
    afisare();
    return 0;
}