Pagini recente » Cod sursa (job #712756) | Cod sursa (job #3219907) | Cod sursa (job #655902) | Cod sursa (job #156198) | Cod sursa (job #3205402)
#include <fstream>
#include <queue>
#include <string>
#define PUTERE 31
#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 size1 = s1.size();
for (int i = 0; i < size1; i++) {
hashPrim1 += (s1[i] * PUTERE) % MOD;
hashPrim2 += (s1[i] * PUTERE2) % MOD;
hashSecund1 += (s2[i] * PUTERE) % MOD;
hashSecund2 += (s2[i] * PUTERE2) % MOD;
}
if (hashPrim1 == hashSecund1 && hashPrim2 == hashSecund2)
{
rez.push(1);
cnt++;
}
for (int i = size1; i < s2.size(); i++)
{
hashSecund1 = (hashSecund1 - ((s2[i - size1] * PUTERE) % MOD) + (s2[i] * PUTERE) % MOD) % MOD;
hashSecund2 = (hashSecund2 - ((s2[i - size1] * PUTERE2) % MOD) + (s2[i] * PUTERE2) % MOD) % MOD;
if (hashPrim1 == hashSecund1 && hashPrim2 == hashSecund2)
{
rez.push(i + 1 - size1);
cnt++;
}
}
cout << cnt << '\n';
while (!rez.empty()) {
cout << rez.front() << " ";
rez.pop();
}
}