Cod sursa(job #2457937)

Utilizator Iulia25Hosu Iulia Iulia25 Data 19 septembrie 2019 09:53:23
Problema Potrivirea sirurilor Scor 32
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.31 kb
#include <fstream>
#include <cstring>

using namespace std;

ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");

long long s1h1, s2h1, s1h2, s2h2, put1 = 1, put2 = 1;
long long mod1 = 100021, mod2 = 100007;
int sol, ans[1005];
string s1, s2;

int main()  {
  fin >> s1 >> s2;
  for (int i = 0; i < s1.size(); ++i)  {
    s1h1 = s1h1 * 27 + s1[i] - 'A' + 1;
    s1h2 = s1h2 * 27 + s1[i] - 'A' + 1;
    put1 *= 27;
    put2 *= 27;
    put1 %= mod1;
    put2 %= mod2;
    s1h1 %= mod1;
    s1h2 %= mod2;
  }
  for (int i = 0; i < s1.size(); ++i)  {
    s2h1 = s2h1 * 27 + s2[i] - 'A' + 1;
    s2h2 = s2h2 * 27 + s2[i] - 'A' + 1;
    s2h1 %= mod1;
    s2h2 %= mod2;
  }
  if (s2h1 == s1h1 && s2h2 == s1h2)  {
    ++sol;
    if (sol <= 1000)
      ans[sol] = 0;
  }
  for (int i = s1.size(); i < s2.size(); ++i)  {
    s2h1 = s2h1 * 27 + s2[i] - 'A' + 1;
    s2h1 = s2h1 - put1 * (s2[i - s1.size()] - 'A' + 1);
    s2h1 = s2h1 % mod1 + mod1;
    s2h1 %= mod1;
    s2h2 = s2h2 * 27 + s2[i] - 'A' + 1;
    s2h2 = s2h2 - put2 * (s2[i - s1.size()] - 'A' + 1);
    s2h2 = s2h2 % mod2 + mod2;
    s2h2 %= mod2;
    if (s2h1 == s1h1 && s2h2 == s1h2)  {
      ++sol;
      if (sol <= 1000)
        ans[sol] = i - s1.size() + 1;
    }
  }
  fout << sol << '\n';
  for (int i = 1; i <= min(sol, 1000); ++i)
    fout << ans[i] << ' ';
  return 0;
}