Pagini recente » Cod sursa (job #2439497) | Cod sursa (job #2913703) | Cod sursa (job #1310778) | Cod sursa (job #1747159) | Cod sursa (job #857200)
Cod sursa(job #857200)
#include <iostream>
#include <fstream>
#include <string>
#define un unsigned
using namespace std;
string x,y;
int z[2000005],v[1005];
int main()
{
ifstream f("strmatch.in");
ofstream g("strmatch.out");
getline(f,x);
getline(f,y);
y=x+'#'+y;
int p=0,r=0,ii=0,jj=1,l=0;
while(y[ii]==y[jj]) ++p,++ii,++jj;
z[1]=p;
r=p;
for(int i=2;i<y.size();++i)
{
if(r<i)
{
l=r=i;
while(r<y.size () && y[r-l]==y[r])
++r;
z[i]=r-l;
--r;
}
else
{
int k=i-l;
if(z[k]<r-i+1 ) z[i]=z[k];
else
{
l=i;
while(r<y.size() && y[r]==y[r-l]) ++r;
z[i]=r-l;
--r;
}
}
if(z[i]==x.size()))
{
v[++v[0]]=i-x.size()-1;
}
}
g<<v[0]<<"\n";
for(int i=1;i<=min(1000,v[0]);++i)
g<<v[i]<<" ";
return 0;
}