Pagini recente » Cod sursa (job #2000197) | Diferente pentru teorema-chineza-a-resturilor intre reviziile 71 si 89 | Cod sursa (job #2752279) | Cod sursa (job #1736263) | Cod sursa (job #1639095)
#include <bits/stdc++.h>
#define longn 2000005
using namespace std;
char s1[longn],s2[longn];
int pref[longn],is2[longn],n,m,ras[1005],sol;
void prefix()
{
int i=0,j=1;
while (j<n)
{
if (s1[i]==s1[j])
{
pref[j]=i+1;///retin poziti, nu lungimi
++i;++j;
}
else
if (i==0)
++j;
else
i=pref[i-1];
}
}
void kmp()
{
int i=0,j=0;
while (j<m)
{
if (s1[i]==s2[j])
{
++i;
++j;
if (i==n)
{
sol++;
if (sol<1001)
ras[sol]=j-n;
}
}
else
{
if (i==0)
++j;
else
i=pref[i-1];
}
}
}
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
fgets(s1,longn,stdin);
scanf("\n");
fgets(s2,longn,stdin);
n=strlen(s1);
m=strlen(s2);
if (s1[n-1]=='\n')
--n;
if (s2[m-1]=='\n')
--m;
prefix();
kmp();
printf("%d\n",sol);
sol=min(1000,sol);
for (int i=1;i<=sol;++i)
printf("%d ",ras[i]);
return 0;
}