Pagini recente » Cod sursa (job #928151) | Cod sursa (job #2531279) | Cod sursa (job #1025050) | Istoria paginii runda/aaaaaa/clasament | Cod sursa (job #2426470)
#include <fstream>
#include <iostream>
#define HASH_BASE 71
#define MODULO1 100007
#define MODULO2 100021
#define MAX 1001
using namespace std;
typedef long long LL;
int position[MAX];
LL hashFunction1(string a)
{
int n = a.length(), i, hashBase = HASH_BASE;
LL hashValue = 0;
for(i = 0; i < n; i++)hashValue = (hashValue * hashBase + a[i]) % MODULO1;
return hashValue;
}
LL hashFunction2(string a)
{
int n = a.length(), i, hashBase = HASH_BASE;
LL hashValue = 0;
for(i = 0; i < n; i++)hashValue = (hashValue * hashBase + a[i]) % MODULO2;
return hashValue;
}
LL ridicare1(int baza, int exponent)
{
int putere = 1;
while(exponent > 0)
{
if(exponent % 2 == 1)putere = putere * baza % MODULO1;
baza = baza * baza % MODULO1;
exponent /= 2;
}
return putere;
}
LL ridicare2(int baza, int exponent)
{
int putere = 1;
while(exponent > 0)
{
if(exponent % 2 == 1)putere = putere * baza % MODULO2;
baza = baza * baza % MODULO2;
exponent /= 2;
}
return putere;
}
int solve(string a, string b)
{
LL hashValueA1, hashValueA2, hashValueC1, hashValueC2;
int n = a.length(), m = b.length(), contor = 0, i;
string c;
hashValueA1 = hashFunction1(a);
hashValueA2 = hashFunction2(a);
c = "";
for(i = 0; i < n; i++)c = c + b[i];
hashValueC1 = hashFunction1(c);
hashValueC2 = hashFunction2(c);
if(hashValueA1 == hashValueC1 && hashValueA2 == hashValueC2)
{
contor++;
if(contor < MAX)position[contor] = 0;
}
for(i = 1; i < m - n + 1; i++)
{
hashValueC1 = (hashValueC1 - b[i - 1] * ridicare1(HASH_BASE, n - 1) % MODULO1) * HASH_BASE % MODULO1 + b[i + n - 1];
hashValueC2 = (hashValueC2 - b[i - 1] * ridicare2(HASH_BASE, n - 1) % MODULO2) * HASH_BASE % MODULO2 + b[i + n - 1];
// cout << hashValueA1 << " " << hashValueC1 << " " << hashValueA2 << " " << hashValueC2 << " " << endl;
if(hashValueA1 == hashValueC1 && hashValueA2 == hashValueC2)
{
contor++;
if(contor < MAX)position[contor] = i;
}
}
return contor;
}
int main()
{
int i, contor;
string a, b;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
fin >> a >> b;
contor = solve(a, b);
fout << contor << '\n';
for(i = 1; i <= min(contor, MAX - 1); i++)fout << position[i] << " ";
fin.close();
fout.close();
}