Pagini recente » Cod sursa (job #2962593) | Cod sursa (job #1816308) | Cod sursa (job #1941651) | Cod sursa (job #2678821) | Cod sursa (job #351183)
Cod sursa(job #351183)
#include<fstream>
#define dmax 2000003
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
char t[dmax],p[dmax];
int urm[dmax],n,m,ap[1002];
void prefix()
{ int k=0,x;
urm[1]=0;
for(x=2;x<=m;x++)
{ while(k>0 && p[k+1]!=p[x])
k=urm[k];
if(p[k+1]==p[x])
k++;
urm[x]=k;
}
}
int main()
{ int i,x=0,nr=0;
in.getline(p,dmax,'\n');
in.getline(t,dmax,'\n');
in.close();
n=strlen(t);
m=strlen(p);
for(i=n;i>=1;i--)
t[i]=t[i-1];
for(i=m;i>=1;i--)
p[i]=p[i-1];
prefix();
for(i=1;i<=n;i++)
{ while(x>0 && p[x+1]!=t[i])x=urm[x];
if(p[x+1]==t[i])x++;
if(x==m)
{ nr++;
ap[nr]=i-m;
x=urm[x];
}
}
out<<nr<<'\n';
for(i=1;i<=1000;i++)
out<<ap[i]<<" ";
out.close();
return 0;
}