Pagini recente » Cod sursa (job #1051248) | Cod sursa (job #2770960) | Cod sursa (job #3256400) | Cod sursa (job #1254861) | Cod sursa (job #2345910)
#include <bits/stdc++.h>
#define MAX 20000001
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char txt[MAX],pat[MAX];
int lps[MAX],i,n,m,len,j,nr,sol[1001];
int main()
{ f.getline(pat,MAX );
f.getline(txt,MAX);
n=strlen(txt);
m=strlen(pat);
for(i=1;i<=1001;i++)
sol[i]=-1;
i=1;
while(i<m)
{ if(pat[len]==pat[i])
{ len++;
lps[i]=len;
i++;
}
else
{
if(len!=0)
len=lps[len-1];
else
{ lps[i]=0;
i++;
}
}
}
i=j=0;
while(i<n)
{ if(txt[i]==pat[j])
{ i++;
j++;
}
else
if(i<n &&pat[j]!=txt[i])
if(j!=0) j=lps[j-1];
else i++;
if(j==m)
{ nr++;
if(nr<=1000) sol[nr]=i-j;
j=lps[j-1];
}
}
g<<nr<<'\n';
for(i=1;i<=1001;i++)
if(sol[i]!=-1)
g<<sol[i]<<" ";
return 0;
}