Cod sursa(job #2722217)

Utilizator Iulia25Hosu Iulia Iulia25 Data 12 martie 2021 17:40:34
Problema Potrivirea sirurilor Scor 18
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.84 kb
#include <fstream>

using namespace std;

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

int n, k, ans;
int z[4000005];
string s1, s2, s;

void Z()  {
  int l = 1, r = 0;
  for (int i = 2; i <= n; ++i)  {
    if (z[i - l + 1] + i < r) {
      z[i] = z[i - l + 1];
      continue;
    }
    int x = 1;
    if (i <= r)
      x = r - i + 1;
    while (x <= i && s[x] == s[i + x - 1])
      ++x;
    --x;
    z[i] = x;
    if (i + x - 1 > r)
      l = i;
    r = i + x - 1;
  }
}

int main()  {
  cin >> s1 >> s2;
  k = s1.size();
  s = "#" + s1 + "#" + s2;
  n = s1.size() + s2.size() + 1;
  Z();
  for (int i = k + 1; i <= n; ++i)
    if (z[i] == k)
      ++ans;
  cout << ans << '\n';
  int cnt = 0;
  for (int i = k + 1; i <= n && cnt < 1000; ++i)  {
    if (z[i] == k)  {
      cout << i - k - 2 << ' ';
      ++cnt;
    }
  }
	return 0;
}