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