Pagini recente » Cod sursa (job #2617295) | Cod sursa (job #2323564) | Cod sursa (job #2880733) | Cod sursa (job #1832145) | Cod sursa (job #1856276)
#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];
int p1 = 0, p2 = 0, p_c1 = 0, p_c2 = 0;
#define MOD1 34919
#define MOD2 41593
#define INV1 11640
#define INV2 27729
int nr = 0;
vector<int> rez;
int main()
{
in >> s2 >> s1;
int l1 = strlen(s1);
int l2 = strlen(s2);
int pw1 = 1;
int pw2 = 1;
for (int i = 0; i < l2; ++i)
{
p1 =(p1 + ((s2[i]) * pw1) % MOD1)%MOD1;
p2 = (p2 + ((s2[i]) * pw2) % MOD2) % MOD2;
pw1 = (pw1 * 3) % MOD1;
pw2 = (pw2 * 3) % MOD2;
}
pw1 = 1;
pw2 = 1;
for (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 * 3) % MOD1;
pw2 = (pw2 * 3) % MOD2;
}
}
if (p1 == p_c1 && p2 == p_c2)
{
rez.push_back(0);
++nr;
}
for (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 (int i = 0; i < rez.size(); ++i)
out << rez[i] << " ";
return 0;
}