Pagini recente » Monitorul de evaluare | Cod sursa (job #1152620) | Cod sursa (job #1152619) | Cod sursa (job #1152616) | Cod sursa (job #1152595)
#include <fstream>
#include <cstring>
#include <bitset>
using namespace std;
bitset<2000005> verif;
char a[2000005],b[2000005];
int n1,n2,i,prec1,prec2,exp1,exp2,sir1,sir2,sol;
const int hash1 = 100007;
const int hash2 = 100021;
int main() {
ifstream f("strmatch.in");
ofstream g("strmatch.out");
f>>a>>b;
n1=strlen(a);
n2=strlen(b);
if(n1>n2) {
g<<"0\n";
return 0;
}
exp1=exp2=1;
for(i=0;i<n1;i++) {
prec1=(prec1*70+a[i])%hash1;
prec2=(prec2*70+a[i])%hash2;
if (i<n1-1) {
exp1=(exp1*70)%hash1;
exp2=(exp2*70)%hash2;
}
}
for(i=0;i<n1;i++) {
sir1=(sir1*70+b[i])%hash1;
sir2=(sir2*70+b[i])%hash2;
}
if(sir1==prec1 && sir2==prec2) {
sol++;
verif[0]=1;
}
for(i=n1;i<n2;i++) {
sir1=((sir1-(b[i-n1]*exp1)%hash1+hash1)%hash1*70+b[i])%hash1;
sir2=((sir2-(b[i-n1]*exp2)%hash2+hash2)%hash2*70+b[i])%hash2;
if(sir1==prec1 && sir2==prec2) {
sol++;
verif[i-n1+1]=1;
}
}
g<<sol<<"\n";
for(i=0;i<n2;i++) {
if(verif[i]==1)
g<<i<<" ";
}
// g<<"\n";
return 0;
}