Pagini recente » Cod sursa (job #2757758) | Cod sursa (job #316862) | Cod sursa (job #2809734) | Cod sursa (job #2566101) | Cod sursa (job #975181)
Cod sursa(job #975181)
//#include <iostream>
#include <fstream>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
string A,B;
#define LE 66666
int suffx[LE];
int i,result[LE],nr_ap;
int nr_res;
int main() {
f>>A>>B;
int na=A.length(),nb=B.length();
int mk=0;
suffx[0]=-1;
for(i=1; i<na; ++i) {
if (A[i]==A[mk]) suffx[i]=++mk;
else {
while (mk>=0&&A[i]!=A[mk])
mk=suffx[mk];
suffx[i]=++mk;
}
}
// for(i=0; i<=na; ++i) cout<<suffx[i]<<'\n';
for(i=0,mk=0; i<nb; ++i)
if(B[i]==A[mk]) {
++ mk;
if (mk==na) {
mk=suffx[na-1];
if (nr_res<1000) result[++nr_res]=i-na+1;
++nr_ap;
}
} else {
while (mk>=0&&B[i]!=A[mk])
mk=suffx[mk];
++mk;
}
g<<nr_ap<<'\n';
// cout<<'\n';
//cout<<nr_ap<<'\n';
for(i=1; i<=nr_res; ++i)
g<<result[i]<<" ";
f.close();
g.close();
return 0;
}