Cod sursa(job #3239865)

Utilizator ChopinFLazar Alexandru ChopinF Data 8 august 2024 11:02:21
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.51 kb
#include <bits/stdc++.h>
#include <vector>
using namespace std;
std::string file = "strmatch";
std::ifstream fin(file + ".in");
std::ofstream fout(file + ".out");
// #define fin std::cin
// #define fout std::cout
const int MOD = 1e9 + 7;
const int P = 31;
const int MAX_MATCHES = 1000;

int charToValue(char c) {
  if (c >= 'a' && c <= 'z')
    return c - 'a' + 1;
  if (c >= 'A' && c <= 'Z')
    return c - 'A' + 27; // 26 letters in lowercase + 1
  if (c >= '0' && c <= '9')
    return c - '0' + 53; // 26 lowercase + 26 uppercase + 1
  return 0;
}
std::vector<long long> hashB;
std::vector<int> matches;
int main(int argc, char *argv[]) {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);

  string A, B;
  fin >> A >> B;

  int lenA = A.size();
  int lenB = B.size();

  long long hashA = 0;
  long long p_pow = 1;
  for (int i = 0; i < lenA; i++) {
    hashA = (hashA + charToValue(A[i]) * p_pow) % MOD;
    p_pow = (p_pow * P) % MOD;
  }

  hashB.resize(lenB + 1, 0);
  p_pow = 1;
  for (int i = 0; i < lenB; i++) {
    hashB[i + 1] = (hashB[i] + charToValue(B[i]) * p_pow) % MOD;
    p_pow = (p_pow * P) % MOD;
  }

  p_pow = 1;
  for (int i = 0; i + lenA <= lenB; i++) {
    long long current_hash = (hashB[i + lenA] + MOD - hashB[i]) % MOD;
    if (current_hash == hashA * p_pow % MOD) {
      matches.push_back(i);
    }
    p_pow = (p_pow * P) % MOD;
  }

  fout << matches.size() << "\n";
  for (int i = 0; i < min((int)matches.size(), MAX_MATCHES); i++) {
    fout << matches[i] << " ";
  }
  fout << "\n";

  return 0;
}