Cod sursa(job #2792621)

Utilizator stefandutastefandutahoria stefanduta Data 2 noiembrie 2021 01:01:43
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.25 kb
#include <stdio.h>
#include <fstream>
#include <string.h>
#define NMAX 2000000

#define HASH_SIZE 666013
#define HASH_BASE 256

using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");

char str[NMAX + 1];
int strLength;

char pattern[NMAX + 1];
int patternLength;

int rez[NMAX], cnt;

void eraseNewLine(char str[], int& length) {
  if (str[length - 1] == '\n')
    str[--length] = 0;
}

int lgput(int a, int n, int mod) {
  int p;

  p = 1;
  while (n) {
    if (n & 1)
      p = (long long)p * a % mod;
    a = (long long)a * a % mod;
    n >>= 1;
  }

  return p;
}

bool cmp(char str[], char pattern[]) {
  int i;

  i = 0;
  while (str[i] && pattern[i] && str[i] == pattern[i])
    ++i;

  return pattern[i] == 0;
}

int computeHash(char str[], int length) {
  int hash, i;

  hash = 0;
  i = 0;
  while (i < length) {
    hash = (hash * HASH_BASE + str[i]) % HASH_SIZE;
    ++i;
  }

  return hash;
}

int addToHash(int hash, char ch) {
  return (hash * HASH_BASE + ch) % HASH_SIZE;
}

int removeFromHash(int hash, char ch, int power) {
  hash -= ch * power % HASH_SIZE;
  if (hash < 0)
    hash += HASH_SIZE;
  return hash;
}

void search(char str[], int strLength, char pattern[], int patternLength) {
  int i, patternHash, strHash, power;
  bool patternFound;

  patternHash = computeHash(pattern, patternLength);
  strHash = computeHash(str, patternLength - 1);

  //out << patternHash << " " << strHash;

  power = lgput(HASH_BASE, patternLength - 1, HASH_SIZE);

  i = patternLength;
  while (i <= strLength && !patternFound) {
    strHash = addToHash(strHash, str[i - 1]);
    if (patternHash == strHash && cmp(str + i - patternLength, pattern))
    {
        cnt++;
        rez[cnt] = i - patternLength;
    }
    strHash = removeFromHash(strHash, str[i - patternLength], power);

    ++i;
  }
}

int main() {

  in.getline(pattern, NMAX);
  patternLength = strlen(pattern);
  eraseNewLine(pattern, patternLength);

  in.getline(str, NMAX);
  strLength = strlen(str);
  eraseNewLine(str, strLength);

  search(str, strLength, pattern, patternLength);

  out << cnt << '\n';
  for (int i = 1; i <= cnt; i++)
    out << rez[i] << " ";

  return 0;
}