Pagini recente » Istoria paginii runda/cosmin_oni2018z2 | Cod sursa (job #1211700) | Istoria paginii runda/pregatire_spartanica_sh/clasament | Profil Ryuzaki | Cod sursa (job #1856285)
#include<fstream>
#include<vector>
#include<iostream>
#include<chrono>
#include<queue>
#include<algorithm>
#include<string.h>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
char s1[2000010], s2[2000010];
unsigned int p1 = 0, p2 = 0, p_c1 = 0, p_c2 = 0;
#define MOD1 60169
#define MOD2 59497
#define INV1 24727
#define INV2 29341
unsigned int nr = 0;
vector<unsigned int> rez;
int main()
{
in >> s2 >> s1;
unsigned int l1 = strlen(s1);
unsigned int l2 = strlen(s2);
unsigned int pw1 = 1;
unsigned int pw2 = 1;
for (unsigned int i = 0; i < l2; ++i)
{
p1 = (p1 + ((s2[i]) * pw1) % MOD1) % MOD1;
p2 = (p2 + ((s2[i]) * pw2) % MOD2) % MOD2;
pw1 = (pw1 * 73) % MOD1;
pw2 = (pw2 * 73) % MOD2;
}
pw1 = 1;
pw2 = 1;
for (unsigned int i = 0; i < l2; ++i)
{
p_c1 = (p_c1 + ((s1[i]) * pw1) % MOD1) % MOD1;
p_c2 = (p_c2 + ((s1[i]) * pw2) % MOD2) % MOD2;
if (i != l2 - 1)
{
pw1 = (pw1 * 73) % MOD1;
pw2 = (pw2 * 73) % MOD2;
}
}
if (p1 == p_c1 && p2 == p_c2)
{
rez.push_back(0);
++nr;
}
for (unsigned int i = l2; i < l1; ++i)
{
p_c1 = ((((MOD1 + p_c1 - s1[i - l2]) % MOD1) * INV1) % MOD1 + (s1[i] * pw1) % MOD1) % MOD1;
p_c2 = ((((MOD2 + p_c2 - s1[i - l2]) % MOD2) * INV2) % MOD2 + (s1[i] * pw2) % MOD2) % MOD2;
if (p1 == p_c1 && p2 == p_c2)
{
++nr;
if (nr <= 1000)
rez.push_back(i - l2 + 1);
}
}
out << nr << "\n";
for (unsigned int i = 0; i < rez.size(); ++i)
out << rez[i] << " ";
return 0;
}