Pagini recente » Cod sursa (job #439855) | Cod sursa (job #448434) | Cod sursa (job #1556620) | Cod sursa (job #342290) | Cod sursa (job #278900)
Cod sursa(job #278900)
//BC
#include <string.h>
#include <stdio.h>
#define lg_max 2000010
char s1[lg_max],s2[lg_max] ;
int lg1,lg2,poz[lg_max];
void citire()
{
freopen ("strmatch.in","r",stdin);
freopen ("strmatch.out","w",stdout);
fgets(s1+1,lg_max,stdin);
lg1=strlen(s1+1);
fgets(s2+1,lg_max,stdin);
lg2=strlen(s2+1);
}
void pre()
{
int k=0;
poz[1]=0;
for (int i=2;i<lg1;i++)
{
while (k && s1[k+1]!=s1[i])
k=poz[k];
if (s1[k+1]==s1[i])
k++;
poz[i]=k;
}
}
void solve()
{
int sol[1010];
int cate=0;
int k=0;
for (int j=1;j<lg2;j++)
{
while (k && s1[k+1]!=s2[j])
k=poz[k];
if (s1[k+1]==s2[j])
k++;
if (k==lg1-1)
{
cate++;
if (cate<1001)
sol[cate-1]=j-lg1+1;
k=poz[k];
}
}
printf("%d\n",cate);
if (cate>1000)
cate=1000;
for (int i=0;i<cate;i++)
printf("%d ",sol[i]);
}
int main ()
{
citire();
pre();
solve();
return 0;
}