Pagini recente » Diferente pentru implica-te/arhiva-educationala intre reviziile 168 si 169 | Cod sursa (job #2296949) | Istoria paginii runda/jc2020-runda1/clasament | Cod sursa (job #432895) | Cod sursa (job #2085514)
#include <fstream>
#include <string.h>
using namespace std;
char T[2000001],P[2000001];
char TT[4000002];
int FF[4000002];
int r,i,rez,n;
ifstream fi("strmatch.in");
ofstream fo("strmatch.out");
int main()
{
fi>>P;
n=strlen(P);
fi>>T;
TT[0]='\0';
strcat(TT,P);
strcat(TT,"*");
strcat(TT,T);
FF[0]=0;
for (i=1;TT[i]!='\0';i++)
{
r=FF[i-1];
while (r>0)
{
if (TT[i]==TT[r])
break;
r=FF[r-1];
}
if (TT[i]==TT[r])
FF[i]=r+1;
else
FF[i]=0;
}
rez=0;
for (i=0;TT[i]!='\0';i++)
if (FF[i]==n)
rez++;
fo<<rez<<"\n";
int nrsol=0;
for (i=0;TT[i]!='\0';i++)
if (FF[i]==n)
{
fo<<i-n-n<<" ";
nrsol++;
if (nrsol==1000)
break;
}
fi.close();
fo.close();
return 0;
}