Pagini recente » Cod sursa (job #488663) | Cod sursa (job #1443970) | Cod sursa (job #1032561) | Cod sursa (job #1312972) | Cod sursa (job #3206238)
#include <fstream>
#include <queue>
#include <string>
#define PUTERE 10
#define PUTERE2 29
#define MOD 100007
using namespace std;
ifstream cin("strmatch.in");
ofstream cout("strmatch.out");
string s1, s2;
queue<int> rez;
int cnt = 0;
int main()
{
///citire
cin >> s1 >> s2;
///daca primul string este mai lung
if (s1.size() > s2.size())
{
cout << 0;
return 0;
}
///calculez hash urile la primul sir
int hashPrim1 = 0, hashPrim2 = 0;
int hashSecund1 = 0, hashSecund2 = 0;
int P1 = 1, P2 = 1;
int size1 = s1.size();
for (int i = 0; i < size1; i++) {
hashPrim1 = (hashPrim1 * PUTERE + s1[i]) % MOD;
hashPrim2 = (hashPrim2 * PUTERE2 + s1[i]) % MOD;
hashSecund1 = (hashSecund1 * PUTERE + s2[i]) % MOD;
hashSecund2 = (hashSecund2 * PUTERE2 + s2[i]) % MOD;
if (i != 0)
{
P1 = (P1 * PUTERE) % MOD;
P2 = (P2 * PUTERE2) % MOD;
}
}
if (hashPrim1 == hashSecund1 && hashPrim2 == hashSecund2)
{
rez.push(1);
cnt++;
}
for (int i = size1; i < s2.size(); i++)
{
hashSecund1 = ((hashSecund1 - (s2[i - size1] * P1) % MOD + MOD) * PUTERE + s2[i]) % MOD;
hashSecund2 = ((hashSecund2 - (s2[i - size1] * P2) % MOD + MOD) * PUTERE2 + s2[i]) % MOD;
if (hashPrim1 == hashSecund1 && hashPrim2 == hashSecund2)
{
rez.push(i + 1 - size1);
cnt++;
}
}
cout << cnt << '\n';
cnt = 0;
while (!rez.empty() && cnt <= 1000) {
cout << rez.front() << " ";
rez.pop();
cnt++;
}
}