Pagini recente » Cod sursa (job #341371) | Cod sursa (job #1946773) | Cod sursa (job #1825937) | Cod sursa (job #1614591)
#include <fstream>
#include <string.h>
#define NMax 2000001
#define BASE 73
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int n, poz[NMax], i, saa, baa;
unsigned long long hashf, p1, p2, foundf;
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*BASE + a[i];
if (i != 0) {
p1 = p1*BASE;
p2 = p2*BASE;
}
}
for (i = 0; i < saa; i++)
foundf = foundf*BASE + b[i];
if (foundf == hashf)
poz[++n] = 0;
for (i = saa; i < baa; i++) {
foundf = foundf - (p1*b[i - saa])*BASE + b[i];
if (foundf == hashf)
poz[++n] = i - saa + 1;
}
g << n << "\n";
for (i = 1; i <= n && i <= 1000; i++)
g << poz[i] << " ";
g << "\n";
return 0;
}