Pagini recente » Cod sursa (job #1010543) | Cod sursa (job #2291954) | Cod sursa (job #1625585) | Cod sursa (job #2373944) | Cod sursa (job #552371)
Cod sursa(job #552371)
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
char p[2000005], t[2000005];
int n, m, b[2000005], a[2000005];
void citire()
{
fgets(p,2000005, stdin);
fgets(t,2000005, stdin);
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;
}