Cod sursa(job #1758396)

Utilizator Burbon13Burbon13 Burbon13 Data 17 septembrie 2016 10:23:46
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 kb
#include <cstdio>
#include <cstring>

using namespace std;

const int nmx = 2000002;

char p[nmx],s[nmx];
int prefix[nmx];
int potriviri[1002];

void citire()
{
    scanf("%s", p);
    scanf("%s", s);
}

void calc_prefix()
{
    int i = 0, j = 1, l = strlen(p);

    while(j < l)
        if(p[j] != p[i])
            if(i == 0)
                ++ j;
            else
                i = prefix[i-1];
        else
        {
            prefix[j] = i + 1;
            ++ j;
            ++ i;
        }
}

void potrivirea()
{
    int i = 0, j = 0, li = strlen(s), lj = strlen(p);

    while(i < li)
        if(s[i] != p[j])
            if(j)
                j = prefix[j-1];
            else
                ++ i;
        else
        {
            ++ i;
            ++ j;
            if(j == lj)
                potriviri[++potriviri[0]] = i - lj;
        }

}

void afish()
{
    printf("%d\n", potriviri[0]);
    for(int i = 1; i <= potriviri[0]; ++i)
        printf("%d ", potriviri[i]);
}

int main()
{
    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);
    citire();
    calc_prefix();
    potrivirea();
    afish();
    return 0;
}