Pagini recente » Cod sursa (job #357214) | Cod sursa (job #2375444) | Cod sursa (job #357258) | Cod sursa (job #2460895) | Cod sursa (job #1614593)
#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[NMax], i, saa, baa;
char a[NMax], b[NMax];
int main()
{
f.get(a, 2000001);
f.get();
f.get(b, 2000001);
p1 = 1;
p2 = 1;
saa = strlen(a);
baa = strlen(b);
for (i = 0; i<saa; 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 (saa > baa) {
g << "0\n";
return 0;
}
for (i = 0; i<saa; i++) {
foundf = (foundf*bs + b[i]) % modf;
founds = (founds*bs + b[i]) % mods;
}
if (foundf == hashf && founds == hashs)
poz[++n] = 0;
for (i = saa; i<baa; i++) {
foundf = ((foundf - (p1*b[i - saa]) % modf + modf)*bs + b[i]) % modf;
founds = ((founds - (p2*b[i - saa]) % mods + mods)*bs + b[i]) % mods;
if (foundf == hashf && founds == hashs)
poz[++n] = i - saa + 1;
}
g << n << "\n";
for (i = 1; i <= n && i <= 1000; i++)
g << poz[i] << " ";
g << "\n";
return 0;
}