Pagini recente » Cod sursa (job #2474455) | Cod sursa (job #3231860) | Cod sursa (job #3159179) | Cod sursa (job #2333556) | Cod sursa (job #2670128)
#include <fstream>
#include <unordered_set>
#include <vector>
using namespace std;
ifstream f("abc2.in");
ofstream g("abc2.out");
int ans;
string s, sub;
unordered_set < string > subs;
string subString(const string &s, int i1, int i2)
{
string sub = "";
for (int i=i1; i<=i2; i++)
sub += s[i];
return sub;
}
void RabinKarp(const string &s, const unordered_set < string > &subs, int &ans)
{
const int base = 256;
const int mod1 = 2000000011;
const int mod2 = 2000000203;
int n = s.size();
int m = (*subs.begin()).size();
unordered_set < int > hsubs1, hsubs2;
for (auto it : subs)
{
int hsub1 = 0;
int hsub2 = 0;
for (int i=0; i<m; i++)
{
hsub1 = (1LL * hsub1 * base + it[i]) % mod1;
hsub2 = (1LL * hsub2 * base + it[i]) % mod2;
hsubs1.insert(hsub1);
hsubs2.insert(hsub2);
}
}
int p1 = 1;
int p2 = 1;
int hs1 = 0;
int hs2 = 0;
for (int i=0; i<m; i++)
{
hs1 = (1LL * hs1 * base + s[i]) % mod1;
hs2 = (1LL * hs2 * base + s[i]) % mod1;
if (i > 0)
{
p1 = (1LL * p1 * base) % mod1;
p2 = (1LL * p2 * base) % mod2;
}
}
string aux;
if (hsubs1.count(hs1) && hsubs2.count(hs2))
ans++;
for (int i=m; i<n; i++)
{
hs1 = (((1LL * hs1 + mod1 - (1LL * p1 * s[i-m]) % mod1) * base) + s[i]) % mod1;
hs2 = (((1LL * hs2 + mod2 - (1LL * p2 * s[i-m]) % mod2) * base) + s[i]) % mod2;
if (hsubs1.count(hs1) && hsubs2.count(hs2))
ans++;
}
}
int main()
{
f >> s;
while (f >> sub)
subs.insert(sub);
RabinKarp(s, subs, ans);
g << ans;
return 0;
}