Pagini recente » Cod sursa (job #2508148) | Cod sursa (job #278572) | Cod sursa (job #2745224) | Monitorul de evaluare | Cod sursa (job #1915430)
#include <cstdio>
#include <cstring>
using namespace std;
char s1[2000010],s[2000010];
int prefix[2000010],n,m,q=0,x=0,pos[2000010],ok=0,ok1=0;
void citire()
{
scanf("%s",s1);
scanf("%s",s);
m=strlen(s1);
n=strlen(s);
}
void prefix1()
{
int i=0,j=1;
while(j<=m-1)
{
if(s1[i]==s1[j])
{
prefix[j]=i+1;
i++;
j++;
}
else if(i!=0)
{
i=prefix[i-1];
}
else
j++;
}
}
void cerinta()
{
int j=0,i=0;
while(i<=n-1)
{
if(s[i]==s1[j])
{
i++;
j++;
if(j==m)
{
pos[0]++;
if(pos[0]<=1000)
pos[pos[0]]=i-m;
}
}
else
if(j)
{
j=prefix[j-1];
}
else
i++;
}
if(pos[0]>=1000)
pos[0]=1000;
printf("%d\n",pos[0]);
for(int i=1;i<=pos[0];i++)
printf("%d ",pos[i]);
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
citire();
prefix1();
cerinta();
//cout << "Hello world!" << endl;
return 0;
}