Pagini recente » Cod sursa (job #1758530) | Cod sursa (job #1322416) | Cod sursa (job #2218773) | Cod sursa (job #804000) | Cod sursa (job #2198361)
#include <bits/stdc++.h>
#define nmax 2000005
#define MOD1 666013
#define MOD2 123451
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int baza = 256;
vector <int> sol;
string A, B;
int hashA1, hashA2, P1=1, P2=1;
int hashB1, hashB2;
int contor;
int main()
{
fin>>A>>B;
int NA=(int)A.size(), NB=(int)B.size();
if(NA > NB) {
fout<<0;
return 0;
}
for(int i=0; i<NA; ++i) {
hashA1=(hashA1*baza+A[i])%MOD1;
hashA2=(hashA2*baza+A[i])%MOD2;
if(i) {
P1=(P1*baza)%MOD1;
P2=(P2*baza)%MOD2;
}
// cout<<hashA1<<' '<<hashA2<<' '<<P1<<' '<<P2<<endl;
}
for(int i=0; i<NA; ++i)
hashB1=(hashB1*baza+B[i])%MOD1,
hashB2=(hashB2*baza+B[i])%MOD2;
if(hashA1 == hashB1 && hashA2 == hashB2) {
++contor;
sol.push_back(0);
}
for(int i=NA; i<=NB; ++i) {
hashB1=((hashB1+MOD1-(B[i-NA]*P1)%MOD1)*baza+B[i])%MOD1;
hashB2=((hashB2+MOD2-(B[i-NA]*P2)%MOD2)*baza+B[i])%MOD2;
// cout<<hashB1<<' '<<hashB2<<endl;
if(hashB1==hashA1 && hashB2==hashA2) {
++contor;
if(contor<=1000) {
sol.push_back(i-NA+1);
}
}
}
fout<<contor<<endl;
for(unsigned i=0; i<sol.size(); ++i) {
fout<<sol[i]<<' ';
}
return 0;
}