Pagini recente » Cod sursa (job #1277892) | Monitorul de evaluare | Monitorul de evaluare | Cod sursa (job #461256) | Cod sursa (job #1282440)
#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[1];
for (i = 1; i < lss; i++)
{
h1 = (h1 * PR + (subsir[i] - 'a')) % MOD1;
h2 = (h2 * PR + (subsir[i] - 'a')) % MOD2;
hq1 = (hq1 * PR + (sir[i] - 'a')) % MOD1;
hq2 = (hq2 * PR + (sir[i] - 'a')) % MOD2;
p1 = (p1 * PR) % MOD1;
p2 = (p2 * PR) % MOD2;
}
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] - 'a')) % MOD1;
hq2 = (((hq2 - p2 * sir[i - lss] + MOD2) % MOD2) * PR + (sir[i] - 'a')) % MOD2;
if (h1 == hq1 && h2 == hq2)
{
n++;
rez.push(i);
}
}
cout << n << "\n";
i = 1000;
while (i && !rez.empty())
{
cout << rez.front() << " ";
rez.pop();
}
return 0;
}