Pagini recente » Cod sursa (job #2057325) | Cod sursa (job #1703698) | Cod sursa (job #476798) | Cod sursa (job #3215021)
#include<bits/stdc++.h>
#pragma GCC optimize("O3")
using namespace std;
const int MOD = 1e9 + 7;
string a, b;
vector<int> ans;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
freopen("strmatch.in", "r", stdin);
freopen("strmatch.out", "w", stdout);
cin >> a >> b;
long long hash1 = 0, hash2 = 0;
for(int i = 0; i < a.size(); i++)
{
hash1 *= 2;
hash1 += (a[i] - 'A');
hash1 %= MOD;
}
for(int i = 0; i < a.size(); i++)
{
hash2 *= 2;
hash2 += (b[i] - 'A');
hash2 %= MOD;
}
if(hash1 == hash2)
ans.push_back(0);
for(int i = a.size(); i < b.size(); i++)
{
hash2 *= 2;
hash2 -= (1LL << a.size()) * (b[i - a.size()] - 'A');
hash2 += (b[i] - 'A');
hash2 %= MOD;
if(hash1 == hash2)
ans.push_back(i - a.size());
cerr << hash1 << " " << hash2 << "\n";
}
cout << ans.size() << "\n";
int n = ans.size();
for(int i = 0; i < min(999, n); i++)
cout << ans[i] + 1<< " ";
}