Pagini recente » Cod sursa (job #1598801) | Cod sursa (job #295905) | Cod sursa (job #364007) | Cod sursa (job #1908691) | Cod sursa (job #2670133)
#include <fstream>
#include <set>
#include <vector>
using namespace std;
ifstream f("abc2.in");
ofstream g("abc2.out");
int ans;
string s, sub;
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 set < string > &subs, int &ans)
{
const int base = 256;
const int mod = 2000000011;
int n = s.size();
int m = (*subs.begin()).size();
set < int > hsubs;
for (auto it : subs)
{
int hsub = 0;
for (int i=0; i<m; i++)
hsub = (1LL * hsub * base + it[i]) % mod;
hsubs.insert(hsub);
}
int p = 1;
int hs = 0;
for (int i=0; i<m; i++)
{
hs = (1LL * hs * base + s[i]) % mod;
if (i > 0)
p = (1LL * p * base) % mod;
}
string aux;
if (hsubs.count(hs) && subs.count(subString(s, 0, m - 1)))
ans++;
for (int i=m; i<n; i++)
{
hs = (((1LL * hs + mod - (1LL * p * s[i-m]) % mod) * base) + s[i]) % mod;
if (hsubs.count(hs) && subs.count(subString(s, i - m + 1, i)))
ans++;
}
}
int main()
{
f >> s;
while (f >> sub)
subs.insert(sub);
RabinKarp(s, subs, ans);
g << ans;
return 0;
}