Pagini recente » Cod sursa (job #2877247) | Cod sursa (job #2867145) | Cod sursa (job #2155392) | Cod sursa (job #1190019) | Cod sursa (job #292607)
Cod sursa(job #292607)
#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[NMAX],p,k;
void mpre()
{ int k=0;
pi[1]=0;
for(int i=2;i<=n;++i)
{ while(k>0&&(N[k+1]!=N[i])) k=pi[k];
if(N[k+1]==N[i]) ++k;
pi[i]=k;
}
}
int main()
{ f.getline(N+1,sizeof(N)-2);
f.getline(M+1,sizeof(M)-2);
N[0]=' ';
M[0]=' ';
n=1;
m=1;
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;
--n;
--m;
mpre();
k=0;
for(i=1;i<=m;++i)
{ while(k>0&&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;
}