Cod sursa(job #2063341)

Utilizator B_RazvanBaboiu Razvan B_Razvan Data 11 noiembrie 2017 10:55:43
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.06 kb
#include <iostream>
#include <cstdio>
#include <cstring>
#define NMAX 2000005

using namespace std;

char s[NMAX], p[NMAX];
int vPS[NMAX], sol[1005];

void prefixSufix()
{
    int l = strlen(p);
    int i=1, j=0;
    vPS[0] = 0;
    while(i < l)
    {
        while(j > 0 && p[j] != p[i])
            j = vPS[j-1];

        if(p[j] == p[i])
            j++;

        vPS[i] = j;
        i++;
    }
}

void gasireSubsir()
{
    int l = strlen(s), lp = strlen(p), j = 0;
    for(int i=0; i<l; ++i)
    {
        while(j > 0 && s[i] != p[j])
            j = vPS[j-1];
        if(s[i] == p[j])
            j++;
        if(j == lp)
        {
            sol[++sol[0]] = i-lp+1;
            if(sol[0] == 1000)
                return;
        }
    }
}

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

    scanf("%s\n%s", &p, &s);

    prefixSufix();
    gasireSubsir();

    printf("%d\n", sol[0]);
    for(int i=1; i<=sol[0]; ++i)
        printf("%d ", sol[i]);
    return 0;
}