Pagini recente » Cod sursa (job #1276347) | Cod sursa (job #2085309) | Cod sursa (job #1054041) | Cod sursa (job #2136370) | Cod sursa (job #1229204)
#include <fstream>
#include <string.h>
#define modf 100007
#define mods 100021
#define NMax 2000001
#define bs 73
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int hashf, hashs, p1, p2, foundf, founds, n, poz[1001], i;
char a[NMax], b[NMax];
int main()
{
f.get(a, 2000001);
f.get();
f.get(b, 2000001);
p1=1;
p2=1;
for (i=0; i<strlen(a); i++) {
hashf=(hashf*bs+a[i])%modf;
hashs=(hashs*bs+a[i])%mods;
if (i!=0) {
p1=(p1*bs)%modf;
p2=(p2*bs)%mods;
}
}
if (strlen(a) > strlen(b)) {
g<<"0\n";
return 0;
}
for (i=0; i<strlen(b); i++) {
foundf=((foundf-(p1*b[i-strlen(a)])%modf+modf)*bs+b[i])%modf;
founds=((founds-(p2*b[i-strlen(a)])%mods+mods)*bs+b[i])%mods;
if (foundf==hashf && founds==hashs)
poz[++n]=i-strlen(a)+1;
}
g<<n<<"\n";
for (i=1; i<=n && i<=1000; i++)
g<<poz[i]<<" ";
g<<"\n";
return 0;
}