Pagini recente » Cod sursa (job #528698) | Cod sursa (job #2385520) | Cod sursa (job #2419160) | Cod sursa (job #1978712) | Cod sursa (job #552363)
Cod sursa(job #552363)
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
char p[2000005], t[2000005];
int n, m, b[2000005], a[2000005];
void citire()
{
gets(p);
gets(t);
m=strlen(p);
n=strlen(t);
}
void kmpPreprocess()
{
int i=0, j=-1;
b[i]=j;
while (i<m)
{
while (j>=0 && p[i]!=p[j])
j=b[j];
i++; j++;
b[i]=j;
}
}
void kmpSearch()
{
int i=0, j=0;
while (i<n)
{
while (j>=0 && t[i]!=p[j])
j=b[j];
i++; j++;
if (j==m)
{
a[++a[0]]=i-j;
j=b[j];
}
}
}
void afisare()
{
printf ("%d\n",a[0]);
for (int i=1; i<=min(1000,a[0]); i++)
printf ("%d ",a[i]);
printf ("\n");
}
int main()
{
freopen ("strmatch.in","r",stdin);
freopen ("strmatch.out","w",stdout);
citire();
kmpPreprocess();
kmpSearch();
afisare();
return 0;
}