Pagini recente » Cod sursa (job #330927) | Cod sursa (job #1191450) | Cod sursa (job #990661) | Cod sursa (job #1881950) | Cod sursa (job #1950552)
#include <iostream>
#include <fstream>
#include <string>
#include <bitset>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
string P,S;
int np,ns;
int NM;
bitset<2000005> SM;
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(np>ns){
out<<0;
return;
}
if(HP1==HS1&&HP2==HS2){
NM++;
SM[0]=1;
}
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)
SM[i-np+1]=1;
}
}
out<<NM<<"\n";
NM=0;
for(int i=0;i<ns&&NM<=1000;i++){
if(SM[i]){
out<<i<<" ";
NM++;
}
}
}
int main(){
read();
hashes();
solve();
return 0;
}