Pagini recente » Cod sursa (job #1546459) | Cod sursa (job #847710) | Cod sursa (job #1048527) | Cod sursa (job #30258) | Cod sursa (job #350739)
Cod sursa(job #350739)
#include<fstream>
#define dmax 2000003
#define dmax2 1003
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
char t[dmax],p[dmax];
int n,m,urm[dmax],sol[dmax2];
void geturm()
{ int i,k=-1;
urm[0]=0;
for(i=1;i<m;i++)
{ while(k>0 && p[k+1]!=p[i])
k=urm[k];
if(p[k+1]==p[i])
k++;
urm[i]=k;
}
}
int main()
{ int i,x=-1;
in.getline(p,dmax,'\n');
in.getline(t,dmax,'\n');
in.close();
n=strlen(t);
m=strlen(p);
geturm();
for(i=0;i<n;i++)
{ while(x>0 && t[i]!=p[x+1])
x=urm[x];
if(t[i]==p[x+1])
x++;
if(x==m-1)
{ sol[0]++;
sol[sol[0]]=i-m+1;
x=urm[x];
}
}
out<<sol[0]<<'\n';
for(i=1;i<=sol[0]&&i<=1000;i++)
out<<sol[i]<<" ";
out.close();
return 0;
}