Pagini recente » Cod sursa (job #1802552) | Cod sursa (job #3138075) | Cod sursa (job #952020) | Cod sursa (job #2675454) | Cod sursa (job #2031721)
#include <iostream>
#include <string.h>
#include <fstream>
using namespace std;
ifstream fi("strmatch.in");
ofstream fo("strmatch.out");
int S[2000010];
char N[2000010];
int n;
char H[2000010];
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++;
if (cont==1000)
;
else
///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;
}