Pagini recente » Cod sursa (job #54274) | Cod sursa (job #1355156) | Cod sursa (job #2939538) | Cod sursa (job #3133120) | Cod sursa (job #3234869)
#include <fstream>
#include <vector>
#define mod 1000000009
#define int long long
using namespace std;
std::vector<int> ans;
std::string s, s2;
int hash1 = 0, hash2 = 0, p = 1;
ifstream cin ("strmatch.in");
ofstream cout ("strmatch.out");
signed main()
{
cin >> s >> s2;
for(int i = s.size() - 1;i >= 0; i--)
{
hash1 = (hash1 + p * (s[i] - 'A')) % mod;
hash2 = (hash2 + p * (s2[i] - 'A')) % mod;
p = (p * 26) % mod;
}
p /= 26;
for(int i = s.size();i < s2.size(); i++)
{
if(hash1 == hash2 && ans.size() < 1000)
ans.push_back(i-s.size());
hash2 = (26 * ((hash2 - (p * (s2[i-s.size()] - 'A')) % mod + 2 * mod) % mod) + s2[i] - 'A') % mod;
}
if(hash1 == hash2 && ans.size() < 1000)
ans.push_back(s2.size() - s.size());
cout << ans.size() << '\n';
for(int i = 0;i < ans.size(); i++)
cout << ans[i] << ' ';
}