Pagini recente » Cod sursa (job #2699669) | Cod sursa (job #1219459) | Cod sursa (job #399857) | Cod sursa (job #1852035) | Cod sursa (job #1812399)
#include <fstream>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
short t[2000001];
unsigned short sol[1001], n, m, nr,i=2,k=0,pos1=0,pos2=0;
string a, b;
int main()
{
f>>a>>b;
n=a.size();
m=b.size();
if(m==n)
{ if(a==b) g<<1<<"\n"<<0;
else g<<0;
return 0;
}
t[0]=-1;t[1]=0;
while(i<n)
if (a[i-1]==a[k])t[i++]=++k;
else
if (k>0) k=t[k];
else t[i++]=0;
while(pos1+pos2<m)
if (a[pos2]==b[pos1+pos2])
if (pos2==n-1)
{ if (++nr<1000) sol[nr-1]=pos1;
if (t[pos2] > -1) pos1+=pos2-t[pos2],pos2=t[pos2];
else pos2=0,pos1++;
}
else pos2++;
else if (t[pos2]>-1) pos1+=pos2-t[pos2],pos2=t[pos2];
else pos2=0,pos1++;
g<<nr<<"\n";
for (int i=0;i<(nr<1000?nr:1000);i++) g<<sol[i]<<" ";
}