Pagini recente » Cod sursa (job #2453865) | Cod sursa (job #258915) | Cod sursa (job #2909666) | Cod sursa (job #2759741) | Cod sursa (job #685690)
Cod sursa(job #685690)
#include<fstream>
#include<string.h>
#define lim 2000005
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char N[lim],M[lim];
long long k,i,p[lim],z,Sol[1300],q,n,m;
int min(int a,int b){
if(a<=b)
return a;
return b;
}
int main (){
f>>(N+1);
f>>(M+1);
n=strlen(N+1);
m=strlen(M+1);
k=0;
p[1]=0;
for(i=2;i<=n;i++){
while(k>0 && N[k+1]!=N[i])
k=p[k];
if(N[k+1]==N[i])
k++;
p[i]=k;
}
q=0;
for(i=1;i<=m;i++){
while(q>0 && N[q+1]!=M[i])
q=p[q];
if(N[q+1]==M[i])
q++;
if(q==n){
z++;
if(z<=1000)
Sol[z]=i-q;
}
}
z=min(z,1000);
g<<z<<"\n";
for(i=1;i<=z;i++)
g<<Sol[i]<<" ";
g<<"\n";
return 0;
}