Pagini recente » Cod sursa (job #272189) | Cod sursa (job #1412869) | Cod sursa (job #1100024) | Cod sursa (job #2157076) | Cod sursa (job #2922869)
#include <bits/stdc++.h>
using namespace std;
#define ll long long
ifstream reader ("strmatch.in");
ofstream writer ("strmatch.out");
const ll mod1 = 1e9 + 7;
const ll mod2 = 1e9 + 9;
const ll baza = 73;
int main()
{
// #ifndef ONLINE_JUDGE
// freopen("input", "r", stdin);
// freopen("output", "w", stdout);
// #endif
string a, b;
reader >> a >> b;
if(b.size() < a.size())
{
writer << 0;
return 0;
}
pair <ll, ll> hashA;
for(auto it : a)
{
hashA.first = (hashA.first * 1LL * baza + it) % mod1;
hashA.second = (hashA.second * 1LL * baza + it) % mod2;
}
// cout << hashA.first << " " << hashA.second << '\n';
pair <ll, ll> hashB;
for(int i = 0; i < a.size(); ++i)
{
hashB.first = (hashB.first * 1LL * baza + b[i]) % mod1;
hashB.second = (hashB.second * 1LL * baza + b[i]) % mod2;
}
// cout << hashB.first << " " << hashB.second << '\n';
vector <ll> matches;
if(hashA == hashB)
matches.emplace_back(0);
pair<ll, ll> val = {1, 1};
for(int i = 0; i <= a.size() - 2; ++i)
{
val.first = (val.first * 1ll * baza) % mod1;
val.second = (val.second * 1ll * baza) % mod2;
}
//cout << "val : " << val.first << " " << val.second << '\n';
int nrMatches = matches.size();
for(int i = a.size(); i < b.size(); ++i)
{
hashB.first = (((hashB.first * 1LL - (b[i - a.size()] * 1LL * val.first) % mod1) % mod1 + mod1) % mod1 * 1LL * baza + b[i]) % mod1;
hashB.second = (((hashB.second * 1LL - (b[i - a.size()] * 1LL * val.second) % mod2) % mod2 + mod2) % mod2 * 1LL * baza + b[i]) % mod2;
//cout << i - a.size() + 1 << ": "<< hashB.first << " " << hashB.second << '\n';
if(hashA == hashB)
{
nrMatches++;
if(matches.size() < 1000)
matches.emplace_back(i - a.size() + 1);
}
}
writer<< nrMatches << '\n';
for(auto it : matches)
writer << it << " ";
return 0;
}