Pagini recente » Cod sursa (job #922572) | Cod sursa (job #1354362) | Cod sursa (job #410742) | Cod sursa (job #386187) | Cod sursa (job #1370380)
#include<fstream>
#include<iostream>
#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[1005];
char P[nmax],T[nmax];
void Prefix(char *P)
{
int q, k=0;
urm[1] = 0;
for(q = 2; q <= m; q++)
{
while(k>0 && P[k+1]!=P[q]) k=urm[k];
if(P[k+1]==P[q]) k++;
urm[q]=k;
}
}
void KMP()
{
Prefix(P);
int i,q=0;
for(i = 1; i <= n; i++)
{
while(q>0 && P[q+1]!=T[i]) q=urm[q];
if(P[q+1]==T[i]) q++;
if(q==m&&contor<1000){ contor++; pozitie_aparitie[contor] = i-m; q=urm[q]; }
}
}
void Afisare()
{
fout<<contor<<'\n';
for(int i=1;i<=contor;i++)
fout<<pozitie_aparitie[i]<<' ';
}
int main()
{
P[0]=' '; T[0]=' ';
fin.getline(P+1,nmax);
fin.getline(T+1,nmax);
n=strlen(T)-1; m=strlen(P)-1;
KMP();
Afisare();
return 0;
}