Pagini recente » Cod sursa (job #313139) | Cod sursa (job #249493) | Cod sursa (job #2365457) | Cod sursa (job #1477003) | Cod sursa (job #390310)
Cod sursa(job #390310)
#include <iostream>
#include <fstream>
using namespace std;
int Urm[2000001], sol[1001];
char T[2000001], P[2000001];
int main() {
fstream f1, f2;
int i, j, p, q, t, k, nr=0;
f1.open("strmatch.in", ios::in);
f1>>P>>T;
f1.close();
p=strlen(P); t=strlen(T);
//construiesc functia prefix pentru T
Urm[0]=0; k=0;
for(i=1; i<p; i++) {
while(k>0 && P[i]!=P[k]) {
k=Urm[k];
}
if(P[i]==P[k]) { k++; }
Urm[i]=k;
}
k=-1;
for(i=0; i<t; i++) {
while(k>0 && T[i]!=P[k+1]) {
k=Urm[k];
}
if(T[i]==P[k+1]) { k++; }
if(k==p-1) {
nr++;
if(nr<=1000) { sol[nr-1]=i-p+1; }
}
}
f2.open("strmatch.out", ios::out);
f2<<nr<<endl;
if(nr>1000) { nr=1000; }
for(i=0; i<nr; i++) {
f2<<sol[i]<<" ";
}
f2<<endl;
f2.close();
return 0;
}