Cod sursa(job #2212451)

Utilizator PetyAlexandru Peticaru Pety Data 14 iunie 2018 10:31:31
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 0.95 kb
#include <bits/stdc++.h>

using namespace std;

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

const int d = 256;
string s1, s2;
int n, m, cnt;
vector<int>v;
const int MOD = 666013;

int main()
{
  fin >> s1 >> s2;
  m = s1.size();
  n = s2.size();
  int p = 1;
  for (int i = 1; i < m; i++) {
    p = (p * d) % MOD;
  }
  int a, b;
  a = b = 0;
  for (int i = 0; i < m; i++) {
    a = (a * d + s1[i]) % MOD;
    b = (b * d + s2[i]) % MOD;
  }
  for (int i = 0; i <= n - m; i++) {
    if (a == b) {
      bool ok = 1;
      for (int j = i; j < i + m; j++)
        if (s1[j - i] != s2[j]) {ok = 0; break;}
      if (ok) {
        cnt++;
        v.push_back(i);
        if (cnt == 1000) break;
      }
    }
    b = (d * (b - p * s2[i] % MOD + MOD) % MOD + s2[i + m]) % MOD;
    if (b < 0)
      b = -b;
  }
  fout << cnt << "\n";
  for (int i = 0; i < v.size(); i++)
    fout << v[i] << " ";
  return 0;
}