Pagini recente » Cod sursa (job #1984285) | Cod sursa (job #3242618) | Cod sursa (job #599092) | Cod sursa (job #1876473) | Cod sursa (job #1981093)
#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
char s1[2000001], s2[2000001], j;
int pozitii[2000001];
int baza[65];
int main() {
FILE *fin, *fout;
int n, hash1, hash2, key1=0, key2=0, x, q1, q2, key1test=0, key2test=0, contor=0, lung, i;
//63
fin = fopen("strmatch.in", "r");
fout = fopen("strmatch.out", "w");
hash1=786433;
hash2=572869;
fscanf(fin,"%s", &s1);
fscanf(fin,"%s", &s2);
n=strlen(s1);
x=1;
lung=strlen(s2);
for(i=n;i>=1;i--){
s1[i]=s1[i-1];
}
for(i=lung;i>=1;i--){
s2[i]=s2[i-1];
}
for(j='a';j<='z';j++){
i=j;
baza[j]=x;
x++;
}
for(j='A';j<='Z';j++){
i=j;
baza[i]=x;
x++;
}
for(i=0;i<=9;i++){
baza[i]=x;
x++;
}
q1=1;
q2=1;
for(i=n;i>=1;i--){
key1=(key1+baza[s1[i]]*q1)%hash1;
q1=q1*63%hash1;
key2=(key2+baza[s1[i]]*q2)%hash2;
q2=q2*63%hash2;
}
q1=1;
q2=1;
for(i=n;i>=1;i--){
key1test=(key1test+baza[s2[i]]*q1)%hash1;
q1=q1*63%hash1;
key2test=(key2test+baza[s2[i]]*q2)%hash2;
q2=q2*63%hash2;
}
x=1;
if(key1test==key1&&key2test==key2){
contor++;
pozitii[x]=i;
x++;
}
q1=q1/63;
q2=q2/63;
for(i=n+1;i<=lung;i++){
key1test=((key1test-baza[s2[i-n]]*q1)*63+baza[s2[i]]+hash1)%hash1;
key2test=((key2test-baza[s2[i-n]]*q2)*63+baza[s2[i]]+hash2)%hash2;
if(key1test==key1&&key2test==key2){
contor++;
pozitii[x]=i-n;
x++;
}
}
fprintf(fout,"%d\n", contor);
for(i=1;i<x;i++){
fprintf(fout,"%d ", pozitii[i]);
}
fclose(fin);
fclose(fout);
return 0;
}