Cod sursa(job #2079722)

Utilizator GoogalAbabei Daniel Googal Data 1 decembrie 2017 19:01:25
Problema Potrivirea sirurilor Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.05 kb
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>

using namespace std;

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

const int d = 26;
const int q = 666013;

int n, m;
string s1, s2;
vector < int > sol;

void find_pat() {
  n = s1.size();
  m = s2.size();
  int h = 1, v1 = 0, v2 = 0;

  for(int i = 0; i <= m - 2; i++) {
    h = (h * d) % q;
  }

  for(int i = 0; i < m; i++) {
    v1 = (d * v1 + s1[i]) % q;
    v2 = (d * v2 + s2[i]) % q;
  }

  for(int i = 0; i <= n - m; i++) {
    if(v1 == v2) {
      int j;
      for(j = 0; j < m; j++) {
        if(s1[i + j] != s2[j])
          break;
      }

      if(j == m)
        sol.push_back(i);
    }

    if(i + m < n) {
      v1 = (d * (v1 - s1[i] * h) + s1[i + m]) % q;
      if(v1 < 0)
        v1 += q;
    }
  }
}

int main()
{
  in >> s2 >> s1;
  find_pat();
  out << sol.size() << '\n';

  for(int i = 0; i < min(1000, (int)sol.size()); i++)
    out << sol[i] << ' ';

  in.close();
  out.close();
  return 0;
}