Pagini recente » Cod sursa (job #808225) | Cod sursa (job #530048) | Cod sursa (job #639940) | Cod sursa (job #1354340) | Cod sursa (job #3030614)
#include <iostream>
#include <fstream>
#include <vector>
#define baza1 256
#define baza2 300
#define mod2 1000000080
#define mod1 1000000007
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
string s, a;
int tot;
vector<int>v;
long long calc(long long n,int baza, int mod)
{
long long x=0;
for (int i = 0; i < n; i++)
{
x = x * baza + s[i];
x %= mod;
}
return x;
}
int main()
{
f >> s >> a;
long long m = s.size();
long long n = a.size();
long long h1 = calc(m,baza1,mod1);
long long h2= calc(m, baza2, mod2);
long long h3 = 0;
long long h4 = 0;
long long put1 = 1, put2 = 1;
for (int i = 0; i < m; i++)
{
put1 *= baza1;
put1 %= mod1;
put2 *= baza2;
put2 %= mod2;
}
for (int i = 0; i < n; i++)
{
h3 = baza1 * h3 + a[i];
h3 %= mod1;
h4 = baza2 * h4 + a[i];
h4 %= mod2;
if (i >= m)
{
h3 = h3 - (a[i - m] * put1) % mod1;
if (h3 < 0)
{
h3 += mod1;
}
h4 = h4 - (a[i - m] * put2) % mod2;
h4 %= mod2;
if (h4 < 0)
{
h4 += mod2;
}
}
if (i >= m-1)
{
if (h1 == h3 && h2==h4)
{
tot++;
v.push_back(i - m + 1);
}
}
}
g << tot << '\n';
int lung = min(1000, (int)v.size());
for (int i = 0; i <= lung - 1; i++)
{
g << v[i] << ' ';
}
}