Pagini recente » Cod sursa (job #1439971) | Cod sursa (job #1579574) | Cod sursa (job #2780001) | Cod sursa (job #3186938) | Cod sursa (job #2223371)
//#include <iostream>
#include <fstream>
#include <cstring>
#include <queue>
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
int lgA, lgB, ap;
char a[2000010], b[2000010];
int t[2000010], v[1005];
int main()
{
int act=0, urm;
cin>>a>>b;
lgA=strlen(a);
lgB=strlen(b);
act = 0;
urm = 1;
t[0] = -1;
while(urm <= lgA)
{
if(a[act] == a[urm])
{
t[urm] = t[act];
++act;
++urm;
}
else
{
t[urm] = act;
do
act = t[act];
while(act >= 0 && a[act] != a[urm]);
++act;
++urm;
}
}
for(int i=0, j=0; j<lgB; )
{
if(a[i] == b[j])
{
++i;
++j;
if(i == lgA)
{
++ap;
if(ap <= 1000)
v[ap] = j-lgA;
i=t[i];
}
}
else
{
i = t[i];
if(i < 0)
{
++i;
++j;
}
}
}
cout<<ap<<'\n';
for(int i=1; i <= min(ap, 1000); ++i)
cout<<v[i]<<' ';
return 0;
}