Pagini recente » Istoria paginii moisil-2017/clasament/9 | Cod sursa (job #1175856) | Cod sursa (job #1531743) | Cod sursa (job #776860) | Cod sursa (job #752844)
Cod sursa(job #752844)
#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,z1=0,y1=0,q1=100013,ch,ch1,h1=1;
for(int i=0; i<m-1; i++){
ch=go(B[i]);
z=z*63+ch; z%=q;
z1=z1*63+ch; z1%=q1;
ch=go(A[i]);
y=y*63+ch; y%=q;
y1=y1*63+ch; y1%=q1;
h*=63;
h%=q;
h1*=63;
h1%=q1;
}
queue<int> Q;
z=z*63+go(B[m-1]); z%=q;
y=y*63+go(A[m-1]); y%=q;
z1=z1*63+go(B[m-1]); z1%=q1;
y1=y1*63+go(A[m-1]); y1%=q1;
bool t;
for(int i=m; i<=n; i++){
if(z==y && z1==y1){
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); }
}
ch=go(A[i]);
ch1=go(A[i-m]);
y=(63*((y-ch1*h)%q+q)+ch)%q;
y1=(63*((y1-ch1*h1)%q1+q1)+ch)%q1;
}
cour << Q.size() << "\n";
int tr=1;
while(!Q.empty() && tr<=1000){
cour << Q.front() << " ";
Q.pop();
tr++;
}
return 0;
}