Cod sursa(job #2462007)

Utilizator Iulia25Hosu Iulia Iulia25 Data 26 septembrie 2019 17:44:27
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.18 kb
#include <fstream>
#include <cstring>

using namespace std;

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

int n, l, r, ans;
int zet[4000005], v[1005];

string s1, s2, s;

int main()  {
  fin >> s1 >> s2;
  s = '#' + s1 + '#' + s2;
  n = s1.size() + s2.size() + 1;
  zet[1] = 1;
  for (int i = 2; i <= n; ++i)  {
    if (i >= r)  {
      l = i;
      int x = 1;
      while (s[i + x - 1] == s[x] && i + x - 1 <= n)
        ++x;
      --x;
      r = i + x - 1;
      zet[i] = x;
      if (x == s1.size())  {
        ++ans;
        if (ans <= 1000)
          v[ans] = i - s1.size() - 2;
      }
      continue;
    }
    if (i + zet[i - l + 1] >= r)  {
      int x = r - i + 1;
      while (s[i + x - 1] == s[x] && i + x - 1 <= n)
        ++x;
      --x;
      r = i + x - 1;
      zet[i] = x;
      if (x == s1.size())  {
        ++ans;
        if (ans <= 1000)
          v[ans] = i - s1.size() - 2;
      }
      l = i;
      continue;
    }
    zet[i] = zet[i - l + 1];
    if (zet[i] == s1.size())  {
      ++ans;
      if (ans <= 1000)
        v[ans] = i - s1.size() - 2;
    }
  }
  fout << ans << '\n';
  for (int i = 1; i <= min(ans, 1000); ++i)
    fout << v[i] << ' ';
  return 0;
}