Cod sursa(job #2457945)

Utilizator Iulia25Hosu Iulia Iulia25 Data 19 septembrie 2019 10:04:41
Problema Potrivirea sirurilor Scor 98
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.38 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;
const long long mod1 = 100021, mod2 = 100007;
int sol, ans[1005], v[1000];
string s1, s2;

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