Pagini recente » Cod sursa (job #3274784) | Cod sursa (job #3285424) | Diferente pentru implica-te/arhiva-educationala intre reviziile 140 si 223 | Cod sursa (job #213944) | Cod sursa (job #579618)
Cod sursa(job #579618)
#include <cstdio>
#include <cstdlib>
#include <cstring>
FILE *fin=fopen("strmatch.in","r");
FILE *fout=fopen("strmatch.out","w");
char s[2000001],w[2000001];
int n,m;
int t[2000001];
void compute_t()
{
int i = 2;
int cnd = 0;
t[0]=-1;
t[1]=0;
while (i<=m)
{
if (w[i-1]==w[cnd])
{
cnd++;
t[i]=cnd;
i++;
} else
if (cnd)
cnd=t[cnd];
else
t[i++] = 0;
}
}
int sn = 0;
int sol[1000];
void solution(int pos)
{
if (sn<1000)
sol[sn]=pos;
sn++;
}
void kmp()
{
int st = 0;
int i = 0;
while (st+i<n)
{
if (i<m && w[i]==s[st+i])
{
i++;
if (i==m)
solution(st);
} else {
st=st+i-t[i];
if (t[i]<0)
i=0;
else
i = t[i];
}
}
}
int main (int argc, char * const argv[]) {
fscanf(fin, "%s%s",s,w);
n = strlen(s);
m = strlen(w);
compute_t();
kmp();
fprintf(fout, "%d\n",sn);
if (sn>1000)
sn=1000;
for (int i=0; i<sn; i++)
fprintf(fout, "%d ",sol[i]);
fclose(fin);
fclose(fout);
return 0;
}