Pagini recente » Cod sursa (job #2965354) | Cod sursa (job #2137492) | Cod sursa (job #1935275) | Cod sursa (job #2273382) | Cod sursa (job #2883865)
#include <fstream>
#include <string>
#include <vector>
#include <cctype>
#include <unordered_map>
using namespace std;
ifstream fin("grader_test28.in");
ofstream fout("strmatch.out");
const int nrlitalfabet = 62, MOD = 1999999973;
long long add(long long a, long long b)
{
long long res = a + b;
while (res >= MOD)
res -= MOD;
while (res < 0)
res += MOD;
return res;
}
int main()
{
string a, b;
vector <int> rez(1000, 0);
unordered_map <char, int> chei;
fin >> a;
fin >> b;
int lung = a.length(), i, j, k=0;
long long hasha=0, putmic = 1, hashb = 0, hashbnou;
char test;
j = 1;
for (test = 'a'; test <= 'z'; test++, j++)
chei[test] = j;
for (test = 'A'; test <= 'Z'; test++, j++)
chei[test] = j;
for (test = '0'; test <= '9'; test++, j++)
chei[test] = j;
if (a.length() > b.length())
fout << 0;
else
{
for(i = lung-1; i >=1; i--)
{
hasha = add(hasha + putmic * chei[a[i]], MOD);
hashb = add(hashb + putmic * chei[b[i]], MOD);
putmic = add(putmic * nrlitalfabet, MOD);
}
hasha = add(hasha + putmic * chei[a[0]],MOD);
hashb = add(hashb + putmic * chei[b[0]],MOD);
if (hasha == hashb)
{
rez[k++] = 0;
}
hashbnou = hashb;
for (i = lung; i < b.length(); i++)
{
j = i - lung + 1;
//hashbnou = (MOD + hashbnou - (chei[b[j - 1]] * putmic % MOD) * nrlitalfabet % MOD + chei[b[i]]) % MOD;
hashbnou = ((MOD + hashbnou - (chei[b[j-1]] * putmic) % MOD) * nrlitalfabet + chei[b[i]]) % MOD;
if (hashbnou == hasha)
{
if (k < 1000)
rez[k++] = j;
}
}
fout << k << '\n';
for (i = 0; i < min(k, 1000); i++)
{
fout << rez[i] << ' ';
}
}
return 0;
}