Pagini recente » Cod sursa (job #1765380) | Cod sursa (job #1072066) | Cod sursa (job #1311321) | Cod sursa (job #1090409) | Cod sursa (job #1259007)
#include <iostream>
#include <fstream>
#include <string>
using namespace std;
int main()
{
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string A, B;
int P(263), P1(1), P2(1),
hashA1(0), hashA2(0),
hashB1(0), hashB2(0),
mod1(100003), mod2(100019),
matches[1001], nr(0);
getline(fin, A);
getline(fin, B);
if (A.size() > B.size()) {
fout << '0' << endl;
return 0;
}
for (size_t i = 0; i < A.size(); ++i) {
hashA1 = (hashA1 * P + A[i]) % mod1;
hashA2 = (hashA2 * P + A[i]) % mod2;
}
for (size_t i = 0; i < A.size(); ++i) {
hashB1 = (hashB1 * P + B[i]) % mod1;
hashB2 = (hashB2 * P + B[i]) % mod2;
if (i != 0) {
P1 = (P1 * P) % mod1;
P2 = (P2 * P) % mod2;
}
}
if (hashA1 == hashB1 && hashA2 == hashB2)
matches[nr++] = 0;
for (size_t i = A.size(); i < B.size(); ++i) {
hashB1 = (((hashB1 - B[i-A.size()] * P1) % mod1 + mod1) * P + B[i]) % mod1;
hashB2 = (((hashB2 - B[i-A.size()] * P2) % mod2 + mod2) * P + B[i]) % mod2;
if (nr < 1000 && hashA1 == hashB1 && hashA2 == hashB2)
matches[nr++] = i - A.size() + 1;
else if(hashA1 == hashB1 && hashA2 == hashB2)
nr++;
}
fout << nr << '\n';
for (int i = 0; i < nr && i < 1000; ++i)
fout << matches[i] << ' ' ;
fout << endl;
return 0;
}