Pagini recente » Cod sursa (job #710410) | Cod sursa (job #58996) | Cod sursa (job #3240062) | Cod sursa (job #605950) | Cod sursa (job #3205395)
#include <fstream>
#include <queue>
#include <string>
#define PUTERE 31
#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 hash1 = 0, hash2 = 0;
int size1 = s1.size();
for (int i = 0; i < size1; i++) {
hash1 += (s1[i] * PUTERE) % MOD;
hash2 += (s2[i] * PUTERE) % MOD;
}
if (hash1 == hash2)
{
rez.push(1);
cnt++;
}
for (int i = size1; i < s2.size(); i++)
{
hash2 = (hash2 - ((s2[i - size1] * PUTERE) % MOD) + (s2[i] * PUTERE) % MOD) % MOD;
if (hash1 == hash2)
{
rez.push(i + 1 - size1);
cnt++;
}
}
cout << cnt << '\n';
while (!rez.empty()) {
cout << rez.front() << " ";
rez.pop();
}
}