Cod sursa(job #1441166)

Utilizator DrumeaVDrumea Vasile DrumeaV Data 23 mai 2015 20:28:12
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.01 kb
#include <bits/stdc++.h>
const int Max=2000000;

char A[Max],B[Max];
int P[Max],Sol[1000],N,M,nr = 0;

void Prefix()
{
    int p = 0;
    P[1] = 0;
    for (int i = 2;i <= N; i++)
    {
        while (p && A[p+1] != A[i])
            p = P[p];
        if (A[p+1] == A[i]) p++;
        P[i] = p;
    }
}

void Read()
{
    freopen("strmatch.in","r",stdin);
    scanf("%s",A+1);
    scanf("%s",B+1);
    N = strlen(A+1);
    M = strlen(B+1);
}

void Write()
{
    freopen("strmatch.out","w",stdout);
    printf("%d\n",nr);
    if (nr > 1000) nr = 1000;
    for ( int i = 1;i <= nr; i++) printf("%d ",Sol[i]);
}

int main()
{
    int i,p = 0;
    Read();
    Prefix();
    for (i = 1;i <= M; i++)
    {
        while (p && A[p+1] != B[i])
            p = P[p];
        if (A[p+1] == B[i])
            p++;
        if (p == N)
        {
            p = P[N];
            nr++;
            if (nr <= 1000)
            Sol[nr] = i-N;
        }
    }
    Write();
    return 0;
}