Pagini recente » Cod sursa (job #2957412) | Cod sursa (job #2317415) | Cod sursa (job #327672) | Cod sursa (job #3159795) | Cod sursa (job #1896389)
#include <fstream>
#include <string>
#define a 10
#define MOD 1000003
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string s1, s2;
int nr;
int main()
{
fin >> s1;
fin >> s2;
long long hash = 0;
long long pow = 1;
for (int i = 0; i < s1.size(); i++)
hash = (hash * a % MOD + s1[i]) % MOD, pow = pow * a % MOD;
long long rolling_hash = 0;
for (int i = 0; i < s1.size(); i++)
rolling_hash = (rolling_hash * a % MOD + s2[i]) % MOD;
if (rolling_hash == hash)
nr++;
for (int i = s1.size(); i < s2.size(); i++)
{
rolling_hash = (rolling_hash * a % MOD - s2[i - s1.size()] * pow % MOD + s2[i]) % MOD;
if (rolling_hash == hash)
nr++;
}
fout << nr;
return 0;
}