Pagini recente » Cod sursa (job #1816537) | Cod sursa (job #2183898) | Cod sursa (job #2788849) | Cod sursa (job #1861981) | Cod sursa (job #854786)
Cod sursa(job #854786)
// Rabin - Karp
#include <fstream>
#include <cstring>
using namespace std;
ifstream f("strmatch.in"); ofstream g("strmatch.out");
const int base=59;
const int nmod1=100003, nmod2=100019;
char a[2000005], b[2000005];
int rez[2000005];
int i, j, n, m, rezt;
int keya, keyb, basepow, keya2, keyb2, basepow2;
inline int convertLetter (char c){
if (c<'a') return c-'A';
return c-'a'+26;
}
int main(){
f>>a>>b;
for (i=0; a[i]!='\0'; i++){
keya=(keya*base+convertLetter(a[i])) % nmod1;
keya2=(keya2*base+convertLetter(a[i])) % nmod2;
n++;
}
basepow=basepow2=1;
for (i=1; i<n; i++) {
basepow=basepow * base % nmod1;
basepow2=basepow2 * base % nmod2;
}
for (i=0; i<n; i++){
keyb=(keyb*base+convertLetter(b[i])) % nmod1;
keyb2=(keyb2*base+convertLetter(b[i])) % nmod2;
}
if (keya==keyb && keya2 == keyb2) rez[++rezt]=0;
for (i=n; b[i]!='0'; i++){
keyb=(((keyb - (basepow*convertLetter(b[i-n])%nmod1) + nmod1) * base + convertLetter(b[i]))) % nmod1;
keyb2=(((keyb2 - (basepow2*convertLetter(b[i-n])%nmod2) + nmod2) * base + convertLetter(b[i]))) % nmod2;
if (keya==keyb && keya2 == keyb2) rez[++rezt]=i-n+1;
}
g<<rezt<<"\n";
for (i=1; i<=rezt && i<=1000; i++) g<<rez[i]<<" ";
}