Pagini recente » Cod sursa (job #1968572) | Cod sursa (job #1529594) | Cod sursa (job #780926) | Cod sursa (job #579510) | Cod sursa (job #1651016)
#include <fstream>
#include <cstring>
using namespace std;
ifstream fi("strmatch.in");
ofstream fo("strmatch.out");
#define mx 2000001
#define mod1 100021
#define mod2 100007
#define P 83
char a[mx], b[mx];
int rez[1000], nr, na, nb, cod1, cod2, has1, has2, poz;
int main(){
int p1, p2, i;
fi.get(a,mx);
fi.get();
fi.get(b,mx);
na = strlen(a);
nb = strlen(b);
if( na > nb ){
fo << 0;
return 0;
}
cod1 = cod2 = 0;
has1 = has2 = 0;
p1 = 1;
p2 = 1;
for( i = 0; i < na - 1; i++ ){
cod1 = (cod1 * P + a[i]) % mod1;
cod2 = (cod2 * P + a[i]) % mod2;
has1 = (has1 * P + b[i]) % mod1;
has2 = (has2 * P + b[i]) % mod2;
p1 = (p1 * P) % mod1;
p2 = (p2 * P) % mod2;
}
cod1 = (cod1 * P + a[i]) % mod1;
cod2 = (cod2 * P + a[i]) % mod2;
has1 = (has1 * P + b[i]) % mod1;
has2 = (has2 * P + b[i]) % mod2;
nr = 0;
if( cod1 == has1 && cod2 == has2 )
rez[nr++] = 0;
for( i = na; i < nb; i++ ){
poz = i - na;
has1 = (( has1 - (p1 * b[poz]) % mod1 + mod1) * P + b[i]) % mod1;
has2 = (( has2 - (p2 * b[poz]) % mod2 + mod2) * P + b[i]) % mod2;
if( has1 == cod1 && has2 == cod2 ){
if( nr < 1000 )
rez[nr] = poz + 1;
nr++;
}
}
fo << nr << "\n";
for( i = 0; i < nr && i < 1000; i++ )
fo << rez[i] << " ";
return 0;
}