Pagini recente » Cod sursa (job #2727750) | Cod sursa (job #542773) | Cod sursa (job #495611) | Cod sursa (job #2498312) | Cod sursa (job #1399947)
#include<string.h>
#include<fstream>
//#include<iomanip>
using namespace std;
// 2000005
#define dim 2000005
//ifstream in("date.in");
//ofstream out("date.out");
fstream in("strmatch.in");
ofstream out("strmatch.out");
char cuv[dim];
char sir[dim];
int lung[dim];
int poz[dim];
int n,m;
int main()
{
int i,j,k,cnt=0;
in>>cuv;
m=strlen(cuv);
in>>sir;
n=strlen(sir);
lung[0]=0;
for(i=1;i<m;++i)
{
k=lung[i-1];
while(k>0)
{
if(cuv[k]==cuv[i]) break;
k=lung[k-1];
}
if(cuv[k]==cuv[i]) lung[i]=k+1;
else lung[i]=0;
}
i=0;
j=0;
while(i<n)
{
if(cuv[j]==sir[i])
{
++i;
++j;
if(j==m)
{
poz[cnt++]=i-j;
//out<<(i-j)<<" ";
//out<<"Gasit pe "<<(i-j)<<"\n";
j=lung[j-1];
}
}
else
{
if(j==0) ++i;
else j=lung[j-1];
}
}
out<<cnt<<"\n";
if(cnt>=1000) cnt=1000;
for(i=0;i<cnt;++i) out<<poz[i]<<" ";
/*
for(i=0;i<m;++i) out<<setw(3)<<cuv[i]; out<<"\n";
for(i=0;i<m;++i) out<<setw(3)<<lung[i]; out<<"\n";
out<<"\n";
for(i=0;i<n;++i) out<<setw(3)<<sir[i]; out<<"\n";
for(i=0;i<n;++i) out<<setw(3)<<i; out<<"\n";
out<<"\n";
*/
return 0;
}