Mai intai trebuie sa te autentifici.
Cod sursa(job #2039698)
Utilizator | Data | 14 octombrie 2017 19:59:18 | |
---|---|---|---|
Problema | Potrivirea sirurilor | Scor | 16 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 1.23 kb |
#include <cstdio>
#include <cstring>
using namespace std;
char w[2000005],s[2000005];
int t[2000005];
int sol[2000005],soll=0;
int main()
{
freopen("strmatch.in","r",stdin);
freopen("strmatch.out","w",stdout);
int lw,ls;
scanf("%s",w+1);
scanf("%s",s+1);
t[0]=-1;
t[1]=0;
lw=strlen(w+1);
for(int i=2;i<=lw;++i)
{
int k=i-1;
while(t[k]!=-1&&w[t[k]+1]!=w[i])
k=t[k];
t[i]=t[k]+1;
}
ls=strlen(s+1);
int wi=1;
int si=0;
while(si+wi<=ls)
{
if(w[wi]==s[si+wi])
{
wi++;
if(wi==lw+1)
{
wi--;
++soll;
sol[soll]=si;
si=si+wi-t[wi];
wi=t[wi]+1;
}
}
else
{
if(t[wi]>0)
{
si=si+wi-t[wi];
wi=t[wi]+1;
}
else
{
si=si+wi;
wi=1;
}
}
}
printf("%d\n",soll);
if(soll>=1000)
soll=1000;
for(int i=1;i<=soll;++i)
printf("%d ",sol[i]);
return 0;
}