Pagini recente » Cod sursa (job #2561683) | Cod sursa (job #1561184) | Cod sursa (job #2304197) | Cod sursa (job #738679) | Cod sursa (job #2827948)
#include <fstream>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int mod=30000001, sigma=62, smax=1000, mod2=30000023;
string a,b;
int v[smax+1];
int char_int(char x){
if(x>='0'&&x<='9'){
return x-'0';
}else if(x>='A'&&x<='B'){
return x-'A'+10;
}else{
return x-'a'+36;
}
}
int main(){
fin>>a>>b;
int na=a.size(), nb=b.size();
if(na<=nb){
int sol=0;
int nra=0, nrb=0, nra2=0, nrb2=0;
for(int i=0;i<na;i++){
nra=(nra*sigma+char_int(a[i]))%mod;
nra2=(nra2*sigma+char_int(a[i]))%mod2;
}
int p=1,p2=1;
for(int i=1;i<na;i++){
p=(p*sigma)%mod;
p2=(p2*sigma)%mod2;
}
for(int i=0;i<nb;i++){
if(i>=na){
nrb=(mod+nrb-(char_int(b[i-na])*p)%mod)%mod;
nrb2=(mod2+nrb2-(char_int(b[i-na])*p2)%mod2)%mod2;
}
nrb=(nrb*sigma+char_int(b[i]))%mod;
nrb2=(nrb2*sigma+char_int(b[i]))%mod2;
if(i>=na-1&&nra==nrb&&nra2==nrb2){
sol++;
if(sol<=smax){
v[sol]=i;
}
}
}
fout<<sol<<"\n";
for(int i=1;i<=sol&&i<=smax;i++){
fout<<v[i]<<" ";
}
}else{
fout<<0<<"\n";
}
return 0;
}