Pagini recente » Cod sursa (job #2941231) | Cod sursa (job #394772) | Cod sursa (job #2376249) | Cod sursa (job #282023) | Cod sursa (job #2211269)
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#define P 73
#define MOD1 100007
#define MOD2 100021
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string A, B;
int numberOfMatches = 0;
vector <int> indexListOfMatches;
void Read(void)
{
fin >> A >> B;
}
int Hash(int charA, int charB)
{
int base = 256;
int primeModulus = 101;
int hashValue;
hashValue = ((charA % primeModulus) * base + (int)charB) % primeModulus;
return hashValue;
}
void Match(void)
{
int lengthA, lengthB;
lengthA = A.size();
lengthB = B.size();
if (lengthA > lengthB)
{
fout << "0\n";
return;
}
int P1 = 1, P2 = 1;
int hashA1 = 0, hashA2 = 0;
for (int i = 0; i < lengthA; i++)
{
hashA1 = (hashA1 * P + A[i]) % MOD1;
hashA2 = (hashA2 * P + A[i]) % MOD2;
if (i != 0)
{
P1 = (P1 * P) % MOD1;
P2 = (P2 * P) % MOD2;
}
}
int hash1 = 0, hash2 = 0;
for (int i = 0; i < lengthA; i++)
{
hash1 = (hash1 * P + B[i]) % MOD1;
hash2 = (hash2 * P + B[i]) % MOD2;
}
if (hash1 == hashA1 && hash2 == hashA2)
{
indexListOfMatches.push_back(0);
numberOfMatches++;
}
for (int i = lengthA; i < lengthB; i++)
{
hash1 = ((hash1 - (B[i - lengthA] * P1) % MOD1 + MOD1) * P + B[i]) % MOD1;
hash2 = ((hash2 - (B[i - lengthA] * P2) % MOD2 + MOD2) * P + B[i]) % MOD2;
if (hash1 == hashA1 && hash2 == hashA2)
{
indexListOfMatches.push_back(i - lengthA + 1);
numberOfMatches++;
}
}
}
void Print(void)
{
fout << numberOfMatches << '\n';
int limitIndex;
if (numberOfMatches > 1000)
{
limitIndex = 1000;
}
else
{
limitIndex = numberOfMatches;
}
for (int i = 0; i < limitIndex; i++)
{
fout << indexListOfMatches.at(i) << ' ';
}
}
int main(void)
{
Read();
Match();
Print();
return 0;
}