Cod sursa(job #2794868)

Utilizator Antonia_onisoruantonia onisoru Antonia_onisoru Data 5 noiembrie 2021 16:31:34
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.03 kb
#include <iostream>
#include <fstream>
#include <stdio.h>
#include <string>

using namespace std;

ifstream in("strmatch.in");

ofstream out("strmatch.out");

const int MAXPOZ = 1000;
const int MOD1 = 666031;
const int MOD2 = 1000007;

const int BASE = 256;

int poz[MAXPOZ];

string str;
int size_str;

string pattern;
int size_pattern;

int main(){
  in>>pattern>>str;
  //out<<pattern<<str<<'\n';

  size_str = str.size();
  size_pattern = pattern.size();

  bool foundPattern;
  int i, j;
  int patternCode1, patternCode2;
  int strCode1, strCode2;
  int pow1, pow2;

  patternCode1 = 0;
  patternCode2 = 0;

  strCode1 = 0;
  strCode2 = 0;

  pow1 = 1;
  pow2 = 1;

  for( i = 0; i < size_pattern; i++ ){
    patternCode1 = ( patternCode1 * BASE + pattern[i] ) % MOD1;
    patternCode2 = ( patternCode2 * BASE + pattern[i] ) % MOD2;

    strCode1 = ( strCode1 * BASE + str[i] ) % MOD1;
    strCode2 = ( strCode2 * BASE + str[i] ) % MOD2;

    if( i > 0 ){
      pow1 = pow1 * BASE % MOD1;
      pow2 = pow2 * BASE % MOD2;
    }
  }

  j = 0;
  foundPattern = 0;
  i = size_pattern;
  //out<<patternCode1<<" "<<patternCode2<<'\n';
  //out<<strCode1<<" "<<strCode2<<'\n';
  while( i <= size_str ){
    //out<<i<<" "<<str[i]<<" "<<j<<" "<<foundPattern<<'\n';
    //out<<patternCode1<<" "<<patternCode2<<'\n';
    //out<<strCode1<<" "<<strCode2<<'\n';
    if( patternCode1 == strCode1 && patternCode2 == strCode2 ){
      foundPattern = 1;
      if( j < 1000 )
        poz[j] = i - size_pattern;
    }
    else
      foundPattern = 0;

    strCode1 = strCode1 - str[i - size_pattern] * pow1 % MOD1;
    strCode2 = strCode2 - str[i - size_pattern] * pow2 % MOD2;

    if( strCode1 < 0 )
      strCode1 += MOD1;
    if( strCode2 < 0 )
      strCode2 += MOD2;

    strCode1 = ( strCode1 * BASE + str[i] ) % MOD1;
    strCode2 = ( strCode2 * BASE + str[i] ) % MOD2;
    i++;
    j += foundPattern;
  }

  out<<j<<'\n';

  for( i = 0; i < j; i++ )
    out<<poz[i]<<" ";
  return 0;
}