Pagini recente » Cod sursa (job #734585) | Cod sursa (job #1097376) | Cod sursa (job #876476) | Cod sursa (job #1100048) | Cod sursa (job #1282446)
#include <iostream>
#include <fstream>
#include <string.h>
#include <queue>
#define LMAX 2000010
#define PR 97
#define MOD1 1336337
#define MOD2 1333333
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
char subsir[LMAX], sir[LMAX];
int n, h1, h2, hq1, hq2, p1, p2;
queue <int> rez;
int main()
{
fin >> subsir >> sir;
int i, ls = strlen(sir), lss = strlen(subsir);
p1 = 1; p2 = 1;
h1 = subsir[0];
h2 = subsir[0];
hq1 = sir[0];
hq2 = sir[0];
for (i = 1; i < lss; i++)
{
h1 = (h1 * PR + subsir[i]) % MOD1;
h2 = (h2 * PR + subsir[i]) % MOD2;
hq1 = (hq1 * PR + sir[i]) % MOD1;
hq2 = (hq2 * PR + sir[i]) % MOD2;
p1 = (p1 * PR) % MOD1;
p2 = (p2 * PR) % MOD2;
}
//cout << h1 << " " << h2 << endl << hq1 << " " << hq2 << endl;
if (h1 == hq1 && h2 == hq2)
{
n = 1;
rez.push(0);
}
for (i = lss; i < ls; i++)
{
hq1 = (((hq1 - p1 * sir[i - lss]) % MOD1 + MOD1) * PR + sir[i]) % MOD1;
hq2 = (((hq2 - p2 * sir[i - lss]) % MOD2 + MOD2) * PR + sir[i]) % MOD2;
//cout << hq1 << " " << hq2 << endl;
if (h1 == hq1 && h2 == hq2)
{
n++;
rez.push(i - lss + 1);
}
}
n = min(n, 1000);
fout << n << "\n";
while (n)
{
fout << rez.front() << " ";
rez.pop();
n--;
}
return 0;
}