Pagini recente » Cod sursa (job #1130879) | Cod sursa (job #1438554) | Cod sursa (job #986739) | Cod sursa (job #1680265) | Cod sursa (job #2228769)
#include <fstream>
#include <algorithm>
#include <cstring>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int nr;
char a[2000005],b[2000005];
int t[2000005], ap[1005];
int main()
{
int lgA, lgB;
fin.getline(a,2000005);
fin.getline(b,2000005);
lgA = strlen(a);
lgB = strlen(b);
t[0]=-1;
for(int prec=0, act=1; act <= lgA; ++act, ++prec)
{
if(a[prec] == a[act])
{
t[act] = t[prec];
}
else
{
t[act] = prec;
do
{
prec=t[prec];
}
while(prec >= 0 && a[prec] != a[act]);
}
}
for(int i=0, j=0; i<lgB; )
{
if(a[j]==b[i])
{
i++;
j++;
if(j==lgA)
{
nr++;
if(nr<=1000) ap[nr]=i-lgA;
}
}
else
{
j=t[j];
if(j==-1)
{
++i;
j=0;
}
}
}
fout<<nr<<'\n';
for(int i=1;i<=min(nr,1000);i++)
{
fout<<ap[i]<<' ';
}
return 0;
}