Pagini recente » Cod sursa (job #2937936) | Cod sursa (job #1911425) | Cod sursa (job #1609070) | Cod sursa (job #1502928) | Cod sursa (job #1950546)
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
string P,S;
int np,ns;
int NM;
vector<int> M;
const int MOD1=10007;
const int MOD2=666013;
const int POW1=79;
const int POW2=73;
int HP1,HP2;
int HS1,HS2;
int POWMAX1,POWMAX2;
void read(){
in>>P>>S;
np=P.size();
ns=S.size();
}
void hashes(){
POWMAX1=1;
POWMAX2=1;
for(int i=0;i<np;i++){
//pattern
HP1=(1LL*HP1*POW1 + P[i])%MOD1;
HP2=(1LL*HP2*POW2 + P[i])%MOD2;
//
if(i){
POWMAX1=(1LL*POWMAX1*POW1)%MOD1;
POWMAX2=(1LL*POWMAX2*POW2)%MOD2;
}
//string
HS1=(1LL*HS1*POW1 + S[i])%MOD1;
HS2=(1LL*HS2*POW2 + S[i])%MOD2;
//
}
}
void solve(){
if(HP1==HS1&&HP2==HS2){
NM++;
M.push_back(0);
}
for(int i=np;i<ns;i++){
HS1=((HS1 - (S[i-np]*POWMAX1)%MOD1 + MOD1)*POW1 + S[i])%MOD1;
HS2=((HS2 - (S[i-np]*POWMAX2)%MOD2 + MOD2)*POW2 + S[i])%MOD2;
if(HP1==HS1&&HP2==HS2){
NM++;
if(NM<=1000)
M.push_back(i-np+1);
}
}
out<<NM<<"\n";
for(auto x : M){
out<<x<<" ";
}
}
int main(){
read();
hashes();
solve();
return 0;
}