Pagini recente » Cod sursa (job #848458) | Cod sursa (job #1612898) | Cod sursa (job #868110) | Cod sursa (job #3145518) | Cod sursa (job #1941236)
#include <cstdio>
#include <iostream>
using namespace std;
int a[2000001],b[2000001],p[2000001],inc[1001];
void calcp (int n){
int l,i;
l=0;
for (i=2;i<=n;i++){
while (l>0 && a[l+1]!=a[i])
l=p[l];
if (a[i]==a[l+1])
l++;
p[i]=l;
}
}
int main()
{
FILE *fin=fopen ("strmatch.in","r");
FILE *fout=fopen ("strmatch.out","w");
int n,m,i,l,sol;
char c;
c=fgetc (fin);
n=m=0;
while (c!='\n'){
a[++n]=c;
c=fgetc (fin);
}
c=fgetc (fin);
while ('A'<=c && c<='Z'){
b[++m]=c;
c=fgetc (fin);
}
calcp (n);
l=0;
sol=0;
for (i=1;i<=m;i++){
while (l>0 && b[i]!=a[l+1])
l=p[l];
if (b[i]==a[l+1])
l++;
if (l==n){
sol++;
if (sol<1000)
inc[sol]=i-l;
l=p[l];
}
}
fprintf (fout,"%d\n",sol);
for (i=1;i<=min(sol,1000);i++)
fprintf (fout,"%d ",inc[i]);
return 0;
}