Pagini recente » Cod sursa (job #908380) | Cod sursa (job #444171) | Borderou de evaluare (job #848696) | Cod sursa (job #2157080) | Cod sursa (job #2031711)
#include <iostream>
#include <string.h>
#include <fstream>
using namespace std;
ifstream fi("strmatch.in");
ofstream fo("strmatch.out");
int S[2000001];
char N[2000001];
int n;
char H[2000001];
int h;
int k,f,nrap, nrsolutii[1001], cont;
int main()
{
fi>>N+1;
n=strlen(N+1);
fi>>H;
h=strlen(H);
/// se construieste sirul S
S[0]=-1;
S[1]=0;
for (int i=2;i<=n;i++)
{
/// se obtine S[i]
k=i-1;
while (S[k]!=-1 && N[S[k]+1]!=N[i])
k=S[k];
if (S[k]==-1)
S[i]=0;
else
S[i]=S[k]+1;
}
nrap=0;
f=0; cont=0;
for (int i=0;i<h;i++)
{
/// se cauta cel mai din dreapta lemming ce supravietuieste literei H[i]
while (f!=-1)
{
if (H[i]==N[f+1])
break;
f=S[f];
}
if (f==-1)
f=0;
else
f++;
if (f==n)
{
nrap++;
++cont;
if(cont<1001) ///nu trebuie scrie mai mult de 1000 solutii
nrsolutii[cont]=i-n+1;
f=S[f];
}
}
fo<<nrap<<'\n';
for( int i=1; i<=cont; ++i)
fo<<nrsolutii[i]<<" ";
fi.close();
fo.close();
return 0;
}