Pagini recente » Cod sursa (job #432454) | Cod sursa (job #1359398) | Cod sursa (job #1647839) | Cod sursa (job #2868108) | Cod sursa (job #2647419)
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <fstream>
#include <set>
#include <map>
#include <string>
#include <random>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
#define MOD 133713
vector<string> table[MOD + 1];
string substring, myString;
int ssHash = 0;
int GetHash(string s)
{
int key = 0;
for (auto const& c : s)
key += (int)c;
key <<= 1;
key %= MOD;
key <<= 13;
key %= MOD;
key <<= 9;
key %= MOD;
key >>= 5;
key %= MOD;
key <<= 11;
return key % MOD;
}
void Insert(string s)
{
int pos = GetHash(s);
table[pos].push_back(s);
}
void Delete(string s)
{
int pos = GetHash(s);
int i = 0;
for (auto const& it : table[pos])
{
if (s.compare(it) == 0)
{
table[pos].erase(table[pos].begin() + i);
}
++i;
}
}
bool Search(string s)
{
int hash = GetHash(s);
if (hash == ssHash)
{
for (const auto& it : table[hash])
{
if (s.compare(it) == 0)
{
Delete(it);
return true;
}
}
}
return false;
}
int main()
{
getline(in, substring);
getline(in, myString);
ssHash = GetHash(substring);
string s;
for (int i = 0; i < myString.size() - 2; i++)
{
for (int k = 0; k < 3; k++)
s.push_back(myString[i + k]);
Insert(s);
s.clear();
}
vector<int> positions;
int cnt = 0;
for (int i = 0; i < myString.size() - 2; i++)
{
for (int k = 0; k < 3; k++)
s.push_back(myString[i + k]);
if (Search(s))
{
if (cnt <= 1000)
positions.push_back(i);
++cnt;
}
s.clear();
}
out << cnt << '\n';
for (auto const& it : positions)
out << it << ' ';
}