Pagini recente » Cod sursa (job #388984) | Cod sursa (job #2472712) | Cod sursa (job #1616334) | Cod sursa (job #641583) | Cod sursa (job #3199648)
#include <fstream>
#include <vector>
#include <string>
#define M1 1000000013
#define M2 1000000007
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
string A, B;
vector <int> rez;
unsigned long long hashA1, hashA2, P1 = 1, P2 = 1, hashB1, hashB2;
int szA, szB, nr = 0;
int main()
{
f >> A >> B;
szA = A.size();
szB = B.size();
if (szA > szB)
{
g << "0";
return 0;
}
//hashuri pentru sirul A
for(int i=0; i<szA; ++i)
{
hashA1 = ((hashA1 * 37) % M1 + A[i]) % M1;
hashA2 = ((hashA2 * 31) % M2 + A[i]) % M2;
if(i!=0)
{
P1 = (P1 * 37) % M1; //P1=37^(SZA-1)
P2 = (P2 * 31) % M2; //P2=31^(SZA-1)
}
}
//hashuri pentru primele szA caractere din B
for(int i=0; i<szA; ++i)
{
hashB1 = ((hashB1 * 37) % M1 + B[i]) % M1;
hashB2 = ((hashB2 * 31) % M2 + B[i]) % M2;
}
if(hashA1 == hashB1 && hashA2 == hashB2)
{
rez.push_back(0);
++nr;
}
//Restul de subsiruri de lungime szA
for(int i=szA; i<=szB; ++i)
{
hashB1 = ((37 * (hashB1 + M1 - (B[i - szA] * P1) % M1)) % M1 + B[i]) % M1;
hashB2 = ((31 * (hashB2 + M2 - (B[i - szA] * P2) % M2)) % M2 + B[i]) % M2;
if(hashB1 == hashA1 && hashB2 == hashA2)
{
rez.push_back(i - szA + 1);
nr++;
}
}
g << nr << '\n';
for(int i=0; i<rez.size() && i<1000; ++i)
g << rez[i] << ' ';
return 0;
}