Pagini recente » Istoria paginii runda/moisil2011 | Cod sursa (job #1427444) | Cod sursa (job #1681469) | Cod sursa (job #3140294) | Cod sursa (job #2147508)
#include <bits/stdc++.h>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
const int LEN_MAX = 2000000;
const int MOD1 = 100003, MOD2 = 100019, BAZA = 74;
string a, b;
int nrAns, hA1, hA2;
vector<int> ansPoz;
void genHash()
{
int p1 = 1, p2 = 1;
for(int i = 1; i < a.length(); i++)
{
p1 = (p1 * BAZA) % MOD1;
p2 = (p2 * BAZA) % MOD2;
}
int h1 = 0, h2 = 0;
for(int i = 0; i < a.length(); i++)
{
h1 = (h1 * BAZA + b[i]) % MOD1;
h2 = (h2 * BAZA + b[i]) % MOD2;
}
if(h1 == hA1 && h2 == hA2)
{
nrAns++;
ansPoz.push_back(0);
}
int st = 0;
for(int dr = a.length(); dr < b.length(); dr++)
{
h1 = (((h1 - p1 * b[st]) % MOD1 + MOD1) * BAZA + b[dr]) % MOD1;
h2 = (((h2 - p2 * b[st]) % MOD2 + MOD2) * BAZA + b[dr]) % MOD2;
st++;
if(h1 == hA1 && h2 == hA2)
{
nrAns++;
if(nrAns <= 1000)
ansPoz.push_back(st);
}
}
}
int main()
{
in >> a >> b;
hA1 = hA2 = 0;
for(int i = 0; i < a.length(); i++)
{
hA1 = (hA1 * BAZA + a[i]) % MOD1;
hA2 = (hA2 * BAZA + a[i]) % MOD2;
}
genHash();
vector<int>::iterator it;
out << nrAns << '\n';
for(it = ansPoz.begin(); it != ansPoz.end(); it++)
out << *it << ' ';
out << '\n';
return 0;
}