Pagini recente » Cod sursa (job #2389963) | Cod sursa (job #2744090) | Cod sursa (job #1114719) | Rezultatele filtrării | Cod sursa (job #2147120)
#include <bits/stdc++.h>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
const int MOD = 100003, BAZA = 74;
string a, b;
vector<int> rest[MOD + 2];
int ans, put, nrAns;
vector<int> ansPoz;
void genHash()
{
int h = 0;
for(int i = 0; i < a.length(); i++)
h = (h * BAZA + b[i] - '0') % MOD;
rest[h].push_back(0);
int st = 0;
for(int dr = a.length(); dr < b.length(); dr++)
{
h -= (put * (b[st] - '0') + MOD) % MOD;
h = (h * BAZA + b[dr] - '0') % MOD;
st++;
rest[h].push_back(st);
}
}
int main()
{
in >> a >> b;
put = 1;
for(int i = 1; i < a.length(); i++)
put = (put * BAZA) % MOD;
genHash();
int ha = 0;
for(int i = 0; i < a.length(); i++)
ha = (ha * BAZA + a[i] - '0') % MOD;
vector<int>::iterator it;
for(it = rest[ha].begin(); it != rest[ha].end(); it++)
{
int poz = *it;
bool ok = true;
for(int i = poz; i < poz + a.length(); i++)
if(b[i] != a[i - poz])
ok = false;
if(ok)
{
nrAns++;
if(nrAns <= 1000)
ansPoz.push_back(poz);
}
}
out << nrAns << '\n';
for(it = ansPoz.begin(); it != ansPoz.end(); it++)
out << *it << ' ';
out << '\n';
return 0;
}