Pagini recente » Cod sursa (job #2123283) | Cod sursa (job #665971) | Cod sursa (job #1240413) | Cod sursa (job #2546856) | Cod sursa (job #854761)
Cod sursa(job #854761)
// Rabin - Karp
#include <fstream>
#include <cstring>
using namespace std;
ifstream f("strmatch.in"); ofstream g("strmatch.out");
const int base=59, base2=101;
char a[2000005], b[2000005];
int rez[2000005];
int i, j, n, m, rezt;
unsigned 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]);
keya2=keya2*base2+convertLetter(a[i]);
n++;
}
basepow=basepow2=1;
for (i=1; i<n; i++) {
basepow*=base;
basepow2*=base2;
}
for (i=0; i<n; i++){
keyb=keyb*base+convertLetter(b[i]);
keyb2=keyb2*base2+convertLetter(b[i]);
}
if (keya==keyb && keya2 == keyb2) rez[++rezt]=0;
for (i=n; b[i]!='0'; i++){
keyb=(keyb - basepow * convertLetter(b[i-n]) )*base + convertLetter(b[i]);
keyb2=(keyb2 - basepow2 * convertLetter(b[i-n]) )*base2 + convertLetter(b[i]);
if (keya==keyb && keya2 == keyb2) rez[++rezt]=i-n+1;
}
g<<rezt<<"\n";
for (i=1; i<=rezt && i<=1000; i++) g<<rez[i]<<" ";
}