Pagini recente » Cod sursa (job #1837414) | Cod sursa (job #502624) | Cod sursa (job #1372733) | Cod sursa (job #2783325) | Cod sursa (job #751769)
Cod sursa(job #751769)
#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 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;
y=y*63+go(A[i]); y%=q;
h*=63;
h%=q;
}
queue<int> Q;
z=z*63+go(B[m-1]); z%=q;
y=y*63+go(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()>999){ break; }
y=(63*((y-go(A[i-m])*h)%q+q)+go(A[i]))%q;
}
cour << Q.size() << "\n";
while(!Q.empty()){
cour << Q.front() << " ";
Q.pop();
}
return 0;
}