Pagini recente » Cod sursa (job #1370689) | Cod sursa (job #2917130) | Cod sursa (job #1197113) | Cod sursa (job #2798697) | Cod sursa (job #2988006)
#include <bits/stdc++.h>
using namespace std;
int main()
{
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
string s, t;
cin >> s >> t;
const int p = 31;
vector <long long> p_pow(max(s.size(), t.size()));
p_pow[0] = 1;
for(int i = 1; i < p_pow.size(); i++)
p_pow[i] = p_pow[i - 1] * p;
vector <long long> h(t.size());
for(int i = 0; i < t.size(); i++)
{
h[i] = (t[i] - 'A' + 1) * p_pow[i];
if(i)
h[i] += h[i - 1];
}
long long hs = 0;
for(int i = 0; i < s.size(); i++)
{
hs += (s[i] - 'A' + 1) * p_pow[i];
}
vector <int> a;
for(int i = 0; i + s.size() - 1 < t.size(); i++)
{
long long cur_h = h[i + s.size() - 1];
if(i)
cur_h -= h[i - 1];
if(cur_h == hs * p_pow[i])
a.push_back(i);
}
cout << a.size() << '\n';
for(auto x:a)
cout << x << ' ';
return 0;
}