Pagini recente » Cod sursa (job #1891290) | Cod sursa (job #1994872) | Cod sursa (job #293459) | Cod sursa (job #22940) | Cod sursa (job #292642)
Cod sursa(job #292642)
#include<fstream>
#define NMAX 2000412
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char N[NMAX],M[NMAX];
int i,j,n,m,pi[NMAX],rez[1200],p,k;
void mpre()
{ int k=0;
pi[1]=0;
for(int i=2;i<=n;++i)
{ while(k&&(N[k+1]!=N[i])) k=pi[k];
if(N[k+1]==N[i]) ++k;
pi[i]=k;
}
}
int main()
{ f.getline(N,NMAX+1);
f.getline(M,NMAX+1);
n=0;
m=0;
while((N[n]>='0'&&N[n]<='9')||(N[n]>='a'&&N[n]<='z')||(N[n]>='A'&&N[n]<='Z'))
++n;
while((M[m]>='0'&&M[m]<='9')||(M[m]>='a'&&M[m]<='z')||(M[m]>='A'&&M[m]<='Z')) ++m;
for(i=n;i;--i) N[i]=N[i-1];N[0]='-';
for(i=m;i;--i) M[i]=M[i-1];M[0]='-';
mpre();
k=0;
for(i=1;i<=m;++i)
{ while(k&&N[k+1]!=M[i]) k=pi[k];
if(N[k+1]==M[i]) ++k;
if(k==n) { k=pi[n];
if(p<1000) rez[++p]=i-n;
}
}
g<<p<<"\n";
if(p>1000) p=1000;
for(i=1;i<=p;++i) g<<rez[i]<<" ";
g<<"\n";
f.close();
g.close();
return 0;
}