Pagini recente » Cod sursa (job #670906) | Cod sursa (job #2837542) | Cod sursa (job #854183) | Cod sursa (job #686703) | Cod sursa (job #1514818)
#include <iostream>
#include <cstdio>
#define lim 2000010
#include <cstring>
using namespace std;
int nr,i,j,n,m,pref_max[lim],rez[1005];
char pc[lim],ic[lim];
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
scanf("%s",&pc);
scanf("\n");
scanf("%s",&ic);
n=strlen(pc);
m=strlen(ic);
pc[n]='0';
ic[n]='0';
i=0,j=1;
while (j<n) ///creez prefixul
{
if (pc[i]!=pc[j]) ///daca e diferit avem doua cazuri
{
if (i==0) ///cand e i=0, mergem pe pozitia urmatoare (adica n-avem o succesiune)
++j;
else
i=pref_max[i-1]; ///daca i>0, ma retrag pe pozitia de pref_max a elementului anterior
}
else
{
pref_max[j]=i+1; ///pun in pref_max
++j;++i; ///cresc indicii
}
}
j=0;i=0;
while (i<m)
{
if (ic[i]!=pc[j])
if (j==0)
++i;
else
j=pref_max[j-1];
else
{
++i;++j;
if (j==n)
{
++nr;
if (nr<=1000)
rez[nr]=i-n;
}
}
}
printf("%d\n",nr);
for (int i=1;i<=nr;++i)
printf("%d ",rez[i]);
return 0;
}