Pagini recente » Cod sursa (job #2148136) | Cod sursa (job #934680) | Cod sursa (job #1236490) | Cod sursa (job #286253) | Cod sursa (job #1144334)
#include <fstream>
#include <string>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int mod1= 12974;
const int mod2= 96235;
const int base= 256;
const int nmax= 2000000;
const int solmax= 1000;
int sol[solmax+1];
int main( ) {
string a, b;
fin>>a>>b;
int h1= a[0], h2= a[0], bm1= 1, bm2= 1;
for ( string::iterator it= a.begin()+1; it!=a.end(); ++it ) {
h1= (h1*base+*it)%mod1, h2= (h2*base+*it)%mod2;
bm1= (bm1*base)%mod1, bm2= (bm2*base)%mod2;
}
int x1= 0, x2= 0;
for ( int i= 0; i<(int)a.size(); ++i ) {
x1= (x1*base+b[i])%mod1, x2= (x2*base+b[i])%mod2;
}
if ( h1==x1 && h2==x2 ) {
++sol[0]; sol[sol[0]]= 1;
}
for ( int i= (int)a.size(); i<(int)b.size(); ++i ) {
x1= (((x1-b[i-(int)a.size()]*bm1%mod1)*base+b[i])%mod1+mod1)%mod1;
x2= (((x2-b[i-(int)a.size()]*bm2%mod2)*base+b[i])%mod2+mod2)%mod2;
if ( h1==x1 && h2==x2 ) {
++sol[0];
if ( sol[0]<=solmax ) {
sol[sol[0]]= i-(int)a.size()+1;
}
}
}
fout<<sol[0]<<"\n";
for ( int i= 1; i<=sol[0] && i<=solmax; ++i ) {
fout<<sol[i]<<" ";
}
fout<<"\n";
return 0;
}