Cod sursa(job #3038098)

Utilizator LukyenDracea Lucian Lukyen Data 26 martie 2023 20:28:41
Problema Potrivirea sirurilor Scor 64
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.34 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

#define LLI long long int
#define P 73
#define MOD1 100007
#define MOD2 100021

int main()
{
  string s1, s2;

  fin >> s1 >> s2;

  int hashA1 = 0, hashA2 = 0;
  int subP1 = 1, subP2 = 1;

  if (s1.length() > s2.length())
  {
    cout << "0\n";
    return 0;
  }

  for (int i = 0; i < s1.length(); i++)
  {
    hashA1 = (hashA1 * P + s1[i]) % MOD1;
    hashA2 = (hashA2 * P + s1[i]) % MOD2;

    if (i != 0)
      subP1 = (subP1 * P) % MOD1,
      subP2 = (subP2 * P) % MOD2;
  }

  int hashB1 = 0, hashB2 = 0;
  for (int i = 0; i < s1.length(); i++)
  {
    hashB1 = (hashB1 * P + s2[i]) % MOD1;
    hashB2 = (hashB2 * P + s2[i]) % MOD2;
  }

  int res = 0;
  vector<int> indx;
  if (hashA1 == hashB1 && hashA2 == hashB2)
    res++, indx.push_back(0);

  for (int i = s1.length(); i < s2.length(); i++)
  {
    hashB1 = ((hashB1 - (s2[i - s1.length()] * subP1) % MOD1 + MOD1) * P + s2[i]) % MOD1;
    hashB2 = ((hashB2 - (s2[i - s1.length()] * subP2) % MOD2 + MOD2) * P + s2[i]) % MOD2;

    if (hashA1 == hashB1 && hashA2 == hashB2)
      res++, indx.push_back(i - s1.length());
  }

  fout << res << "\n";
  for (int i = 0; i < indx.size() && i < 1000; i++)
    fout << indx[i] + 1 << " ";

  return 0;
}