Pagini recente » Cod sursa (job #2487193) | Cod sursa (job #2096341) | Cod sursa (job #827499) | Rating Rares Stefanoiu (Rares_Stefanoiu) | Cod sursa (job #1514826)
#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);
gets(pc);
gets(ic);
n=strlen(pc);
m=strlen(ic);
if (pc[n-1]=='\n')
pc[n]=0;
if (ic[m-1]=='\n')
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;
}