Pagini recente » Cod sursa (job #181317) | Cod sursa (job #2514757) | Cod sursa (job #2063361) | Cod sursa (job #918727) | Cod sursa (job #749996)
Cod sursa(job #749996)
#include <iostream>
#include <fstream>
#include <queue>
using namespace std;
int go(char a){
int u=int(a);
if(u<91 && u>64){ return(u-64); }
if(u>96 && u<123){ return(u-70); }
if(u<58){ return(u+5); }
}
int main(){
ifstream cinr ("strmatch.in");
ofstream cour ("strmatch.out");
string A, B;
cinr >> B;
cinr >> A;
int n=A.size(), m=B.size();
int a[n], b[m],r,q=100007,h=1,z=0,y=0;
for(int i=0; i<m-1; i++){
z=z*63+go(B[i]); z%=q;
a[i]=go(A[i]);
y=y*63+a[i]; y%=q;
h*=63;
h%=q;
}
queue<int> Q;
z=z*63+go(B[m-1]); z%=q;
a[m-1]=go(A[m-1]);
y=y*63+a[m-1]; y%=q;
bool t;
for(int i=m; i<=n; i++){
if(z==y){
t=true;
for(int j=0; j<m; j++){
if(A[j+i-m]!=B[j]){ t=false; break; }
}
if(t){ Q.push(i-m); }
}
if(Q.size()>1000){ break; }
a[i]=go(A[i]);
y=(63*((y-a[i-m]*h)%q+q)+a[i])%q;
}
cour << Q.size() << "\n";
while(!Q.empty()){
cour << Q.front() << " ";
Q.pop();
}
return 0;
}