Pagini recente » Cod sursa (job #3289371) | Cod sursa (job #2244425) | Cod sursa (job #3191077) | Cod sursa (job #7285) | Cod sursa (job #2183908)
#include <fstream>
#include <string>
#include <vector>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int base= 256;
const int mod1= 666013;
const int mod2= 123451;
int n;
string a, b;
vector <int> sol;
int main( ) {
fin>>a>>b;
if ( (int)a.size()>(int)b.size() ) {
fout<<"0\n";
return 0;
}
int h1= 0, h2= 0, p1= 1, p2= 1;
for ( int i= 0; i<(int)a.size(); ++i ) {
h1= (h1*base+a[i])%mod1;
h2= (h2*base+a[i])%mod2;
if ( i>0 ) {
p1= (p1*base)%mod1;
p2= (p2*base)%mod2;
}
}
int b1= 0, b2= 0;
for ( int i= 0; i<(int)a.size(); ++i ) {
b1= (b1*base+b[i])%mod1;
b2= (b2*base+b[i])%mod2;
}
if ( b1==h1 && b2==h2 ) {
++n;
sol.push_back(0);
}
for ( int i= (int)a.size(); i<(int)b.size(); ++i ) {
b1= (((b1-b[i-(int)a.size()]*p1)*base+b[i])%mod1+mod1)%mod1;
b2= (((b2-b[i-(int)a.size()]*p2)*base+b[i])%mod2+mod2)%mod2;
if ( b1==h1 && b2==h2 ) {
++n;
if ( n<=1000 ) {
sol.push_back(i-(int)a.size()+1);
}
}
}
fout<<n<<"\n";
for ( int i= 0; i<(int)sol.size(); ++i ) {
fout<<sol[i]<<" ";
}
fout<<"\n";
return 0;
}