Pagini recente » Rating Retegan Mihai (reteganmihai) | Cod sursa (job #885042) | Cod sursa (job #1431760) | Cod sursa (job #995508) | Cod sursa (job #1830969)
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
char a[2000005],c[2000005];
int b[2000005];
int aparitii[2000005];
//
//1
//474
int main()
{
freopen("strmatch.in","r",stdin);
// freopen("strmatch.out","w",stdout);
gets(a);
gets(c);
int n=strlen(a);
int i=1;
int j=0;
b[0]=0;
while(i<n)
{
if(a[i]==a[j])
{
b[i]=j+1;
j++;
i++;
}
else
{
if(j==0)
{
b[i]=0;
i++;
}
else
{
while(a[i]!=a[j])
{
j--;
j=b[j];
if(j==0)
{
b[i]=0;
i++;
break;
}
}
}
}
}
j=0;
int apar=0;
int l = strlen(c);
for(int i=0; i<l; i++)
{
if(c[i]==a[j])
{
j++;
}
else
{
if(j!=0)
{
j=b[j-1];
i--;
}
}
if(j==n)
{
aparitii[apar]=i-n+1;
apar++;
j = b[j - 1];
i--;
}
}
printf("%d\n", apar);
if(apar>1000)
apar=1000;
for(int i=0;i<apar;i++)
printf("%d ", aparitii[i]);
return 0;
}