Cod sursa(job #2063267)

Utilizator B_RazvanBaboiu Razvan B_Razvan Data 11 noiembrie 2017 10:27:55
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.17 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 poz = 0;
    for(int i=0; i<l; ++i)
    {
        if(p[poz] == p[i] && i != poz)
        {
            vPS[i] = vPS[i-1] + 1;
            poz++;
        }
        else
        {
            poz = 0;
            if(p[poz] == p[i] && i != poz)
                vPS[i] = 1;
        }
    }
}

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-j+1;
            j = vPS[lp];
            if(sol[0] == 1000)
                return;
        }
    }
}

int main()
{
    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);
    scanf("%s\n%s", &s, &p);
    prefixSufix();
    gasireSubsir();
    printf("%d\n", sol[0]);
    for(int i=1; i<=sol[0]; ++i)
        printf("%d ", sol[i]);
    return 0;
}