Pagini recente » Cod sursa (job #939959) | Cod sursa (job #2310316) | Cod sursa (job #2328777) | Cod sursa (job #1594127) | Cod sursa (job #2147096)
#include <bits/stdc++.h>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
const int MOD = 100003, BAZA = 27;
string a, b;
vector<int> rest[MOD + 2];
int ans, put;
vector<int> ansPoz;
void genHash()
{
int h = 0;
for(int i = 0; i < a.length(); i++)
h = ((h + BAZA * (b[i] - 'A')) * BAZA) % MOD;
rest[h].push_back(0);
int st = 0;
for(int dr = a.length(); dr < b.length(); dr++)
{
h -= put * (b[st] - 'A');
h = ((h + BAZA * (b[dr] - 'A')) * BAZA) % MOD;
st++;
rest[h].push_back(st);
}
}
int main()
{
in >> a >> b;
put = BAZA;
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] - 'A')) * BAZA) % 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)
ansPoz.push_back(poz);
}
out << ansPoz.size() << '\n';
for(it = ansPoz.begin(); it != ansPoz.end(); it++)
out << *it << ' ';
out << '\n';
return 0;
}