Pagini recente » Cod sursa (job #1548817) | Cod sursa (job #1177748) | Cod sursa (job #862528) | Cod sursa (job #1137645) | Cod sursa (job #1370150)
#include<fstream>
#include<string.h>
#define nmax 2000005
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int n,m,contor,urm[nmax],pozitie_aparitie[nmax];
char P[nmax],T[nmax];
void Prefix()
{
int q, k=-1;
n=strlen(T); m=strlen(P);
urm[0] = 0;
for(q = 1; q < m; q++)
{
while(k>0 && P[k+1]!=P[q]) k=urm[q];
if(P[k+1]==P[q]) k++;
urm[q]=k;
}
}
void KMP()
{
int i,q=-1;
for(i = 0; i < n; i++)
{
while(q>0 && P[q+1]!=T[i]) q=urm[q];
if(P[q+1]==T[i]) q++;
if(q==m-1) { contor++; pozitie_aparitie[contor] = i-m+1; }
}
}
void Afisare()
{
fout<<contor<<'\n';
for(int i=1;i<=contor&&i<=1000;i++)
fout<<pozitie_aparitie[i]<<' ';
fout<<'\n';
fout.close();
}
int main()
{
fin.getline(P,sizeof(P));
fin.getline(T,sizeof(T));
fin.close();
Prefix();
KMP();
Afisare();
return 0;
}