Pagini recente » Cod sursa (job #528369) | Cod sursa (job #805266) | Cod sursa (job #609607) | Cod sursa (job #899380) | Cod sursa (job #3029910)
#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;
int calc(int n,int baza, int mod)
{
int x=0;
for (int i = 0; i < n; i++)
{
x = x * baza + s[i];
x %= mod;
}
return x;
}
int main()
{
f >> s >> a;
int m = s.size();
int n = a.size();
int h1 = calc(m,baza1,mod1);
int h2= calc(m, baza2, mod2);
int h3 = 0;
int h4 = 0;
int 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 + mod1 - ((a[i - m] * put1)%mod1);
h3%= mod1;
h4 = h4 + mod2 - ((a[i - m] * put2) % mod2);
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] << ' ';
}
}