Cod sursa(job #954986)

Utilizator RaduDoStochitoiu Radu RaduDo Data 30 mai 2013 16:19:03
Problema Cifra Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.2 kb
#include<iostream>
#include<cstdio>
#define maxn 100010
using namespace std;
int a[maxn],b[maxn],pi[maxn],pos[maxn],i,q,n,m,ct,ante,x;

//Construirea prefixelor, metodă specifică algoritmului Knuth-Morris-Pratt
void KMP()
{
    int i,q=0;
    for(i=2, pi[1]=0; i<=m; ++i)
    {
        while(q && a[q+1]!=a[i])
            q=pi[q];
        if(a[q+1]==a[i])
            ++q;
        pi[i]=q;
    }
}

int main()
{
    freopen("lambda.in","r",stdin);
    freopen("lambda.out","w",stdout);
    scanf("%d%d",&n,&ante);
    for(i=1; i<n; ++i)
    {
        scanf("%d",&x);
        b[i]=x-ante;
        ante=x;
    }
    scanf("%d",&m);
    for(i=1; i<=m; ++i) scanf("%d",&a[i]);

    KMP();

    //Căutarea celui de-al doilea tablou în primul cu o complexitate redusă de la O(n*m)
    //la O(n+m) cu ajutorul prestabilirii prefixelor
    for(i=1; i<=n; ++i)
    {
        while(q && a[q+1]!=b[i])
            q=pi[q];
        if(a[q+1]==b[i])
            ++q;
        if(q==m)
        {
            q=pi[m];
            pos[++ct] = i-m;
        }
    }

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