Pagini recente » Cod sursa (job #2133923) | Cod sursa (job #2570748) | Cod sursa (job #2528122) | Cod sursa (job #1272195) | Cod sursa (job #954986)
Cod sursa(job #954986)
#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;
}