Cod sursa(job #2289211)

Utilizator ana.pintiliciucAna Maria Pintiliciuc ana.pintiliciuc Data 24 noiembrie 2018 11:55:26
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.91 kb
#include <cstdio>
#define lmax 2000005
#include <cstring>

using namespace std;

char a[lmax], b[lmax];
int p[lmax], n , m, nr, poz[1005];

void construire()
{
    int i=0, j=-1;
    p[0]=-1;
    while(i<m)
    {
        while(j>=0 && a[i]!=a[j])
            j=p[j];
        i++;
        j++;
        p[i]=j;
    }

}

int main()
{
    freopen("strmatch.in",  "r", stdin);
    freopen("strmatch.out",  "w", stdout);
    scanf("%s\n%s", a, b);
    m=strlen(a);
    n=strlen(b);
    construire();
    int i=0, j=0;
    while(i<n)
    {
        while(j>=0 && b[i]!=a[j])
            j=p[j];
        i++;
        j++;
        if(j==m)
        {
            j=p[j];
            nr++;
            if(nr<=1000)
                poz[nr]=i-m;
        }
    }
    printf("%d\n", nr);
    if(nr>1000)
        nr=1000;
    for(int i=1;i<=nr;i++)
        printf("%d ", poz[i]);

    return 0;
}