Pagini recente » Cod sursa (job #2836729) | Cod sursa (job #667918) | Cod sursa (job #2079187) | Cod sursa (job #307670) | Cod sursa (job #182024)
Cod sursa(job #182024)
#include <fstream>
#include <string.h>
#define NMAX 2000001
using namespace std;
int Urm[NMAX];
char T[NMAX], P[NMAX];
int n, m, nrez, rez[1001];
void prefix(char *P){
int k=-1, x;
Urm[0]=-1;
for(x=1; x<m; x++){
while(k>=0 && P[k+1]!=P[x]) k=Urm[k];
if(P[k+1]==P[x]) k++;
Urm[x]=k;
}
}
int main(){
int i, x=-1;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
f.getline(P, NMAX);
f.getline(T, NMAX);
n=strlen(T); m=strlen(P);
prefix(P);
for(i=0; i<n; i++){
while(x>=0 && P[x+1]!=T[i]) x=Urm[x];
if(P[x+1]==T[i]) x++;
if(x==m-1){
if(nrez<1000)rez[nrez++]=i-m+1;
else nrez++;
x=Urm[x];
}
}
g<<nrez<<"\n";
if(nrez>1000) nrez=1000;
for(i=0; i<nrez; i++)
g<<rez[i]<<" ";
return 0;
}