Pagini recente » Cod sursa (job #353305) | Clasament how_fast_can_you_type | Cod sursa (job #1086871) | Cod sursa (job #515091) | Cod sursa (job #2177445)
#include <fstream>
using namespace std;
ifstream fi ("strmatch.in");
ofstream fo ("strmatch.out");
char cuv[2000005],sir[2000005];
int loc[2000005];
int pozpref,pozcuv,pozsir,lgcuv,lgsir;
int nrsol,sol[1005];
void precalc()
{
loc[1]=0;
pozpref=0;
for (pozcuv=2;pozcuv<=lgcuv;pozcuv++)
{
while (pozpref>0 and cuv[pozpref+1]!=cuv[pozcuv]) pozpref=loc[pozpref];
if (cuv[pozpref+1]==cuv[pozcuv]) pozpref++;
loc[pozcuv]=pozpref;
}
}
int main()
{
string a,b;
fi>>a>>b;
for (int i=1;i<=a.size();i++) cuv[i]=a[i-1];
for (int i=1;i<=b.size();i++) sir[i]=b[i-1];
lgcuv=a.size();lgsir=b.size();
precalc();
pozcuv=0;
for (pozsir=1;pozsir<=lgsir;pozsir++)
{
while (pozcuv>0 and cuv[pozcuv+1]!=sir[pozsir]) pozcuv=loc[pozcuv];
if (cuv[pozcuv+1]==sir[pozsir]) pozcuv++;
if (pozcuv==lgcuv)
{
pozcuv=loc[pozcuv];
nrsol++;
sol[nrsol]=pozsir-lgcuv;
}
}
fo<<nrsol<<'\n';
for (int i=1;i<=min(1000,nrsol);i++) fo<<sol[i]<<' ';
fo<<'\n';
return 0;
}