Pagini recente » Cod sursa (job #2428383) | Cod sursa (job #246837) | Cod sursa (job #2215727) | Cod sursa (job #1622673) | Cod sursa (job #1178279)
#include<fstream>
#include<cstring>
using namespace std;
int n,m;
int rez[2000005];
char T[2000005],P[2000005];
int nr,v[1001];
void prefix()
{
int k,q;
rez[1]=0;
k=0;
for (q=2;q<=m;++q)
{
while (k>0 && P[k+1]!=P[q]) k=rez[k];
if (P[k+1]==P[q]) ++k;
rez[q]=k;
}
}
int main()
{
int i;
fstream f("strmatch.in",ios::in);
fstream g("strmatch.out",ios::out);
f.getline(P,2000001);
f.getline(T,2000001);
n=strlen(T);m=strlen(P);
for (i=n-1;i>=0;--i) T[i+1]=T[i];
for (i=m-1;i>=0;--i) P[i+1]=P[i];
prefix();
int q=0;
for (i=1;i<=n;++i)
{
while (q>0 && P[q+1]!=T[i])
q=rez[q];
if (P[q+1]==T[i]) q=q+1;
if (q==m)
{
q=rez[q];
++nr;
if (nr<=1000) v[nr]=i-m;
}
}
g<<nr<<'\n';
if (nr>1000)
for (i=1;i<=1000;++i) g<<v[i]<<' ';
else for (i=1;i<=nr;++i) g<<v[i]<<' ';
return 0;
}