Pagini recente » Cod sursa (job #2069149) | Cod sursa (job #1716038) | Cod sursa (job #2960135) | Cod sursa (job #783923) | Cod sursa (job #966428)
Cod sursa(job #966428)
#include <iostream>
#include <fstream>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
#include <string>
string a,b;
#define LE 2000666
int prfx[LE];
int mnow,i;
int R[LE];
int main() {
f>>a>>b;
int N1=a.length();
int N2=b.length();
mnow=0;
prfx[0]=0;
for(i=1; i<N1; ++i)
if (a[i]==a[mnow]) prfx[i]=++mnow;
else {
while (mnow!=0&&a[i]!=a[mnow])
mnow=prfx[mnow-1];
prfx[i]=mnow;
if (mnow==0&&a[i]==a[mnow]) prfx[i]=++mnow;
}
mnow=0;
int result=0,K=0;
for(i=0; i<N2; ++i)
if (b[i]==a[mnow]) {
++mnow;
if (mnow==N1) {
++result;
mnow=prfx[mnow-1];
if (result<1000)
R[++K]=i-N1+1;
}
} else {
while (mnow!=0&&b[i]!=a[mnow])
mnow=prfx[mnow-1];
prfx[i]=mnow;
if (mnow==0&&b[i]==a[mnow]) prfx[i]=++mnow;
}
g<<result<<'\n';
for(i=1;i<=K;++i) g<<R[i]<<" ";
f.close();
g.close();
return 0;
}