Pagini recente » Cod sursa (job #297847) | Cod sursa (job #1745424) | Cod sursa (job #2387339) | Cod sursa (job #1974097) | Cod sursa (job #1009254)
#include<fstream>
#include<cstring>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
const int Nmax = 2000005;
const int MOD1 = 110503;
const int MOD2 = 104325;
const int a = 62;
char A[Nmax],B[Nmax];
int N,M;
int hashA1,hashB1,alam1=1;
int hashA2,hashB2,alam2=1;
int sol[1005],rasp;
int toi(char c){
if('0'<=c && c<='9') return (int)(c-'0');
if('a'<=c && c<='z') return (int)(c-'a')+10;
if('A'<=c && c<='Z') return (int)(c-'A')+36;
}
void checkEq(int i){
if(hashA1==hashB1 && hashA2==hashB2){
rasp++;
if(rasp<=1000) sol[rasp]=i-M+1;
}
}
int main(){
int i;
in.getline(B,Nmax);
in.getline(A,Nmax);
N=strlen(A);
M=strlen(B);
for(i=0;i<M;i++){
hashA1=(hashA1*a+toi(A[i]))%MOD1;
hashB1=(hashB1*a+toi(B[i]))%MOD1;
hashA2=(hashA2*a+toi(A[i]))%MOD2;
hashB2=(hashB2*a+toi(B[i]))%MOD2;
alam1=(alam1*a)%MOD1;
alam2=(alam2*a)%MOD2;
}
checkEq(i-1);
for(;i<N;i++){
hashA1=((hashA1*a)%MOD1+(-(alam1*toi(A[i-M]))%MOD1+MOD1)+toi(A[i]))%MOD1;
hashA2=((hashA2*a)%MOD2+(-(alam2*toi(A[i-M]))%MOD2+MOD2)+toi(A[i]))%MOD2;
checkEq(i);
}
out<<rasp<<'\n';
for(i=1;i<=(rasp<1000?rasp:1000);i++) out<<sol[i]<<' ';
return 0;
}