Cod sursa(job #2736300)

Utilizator bogdanvladmihaiBogdan Vlad-Mihai bogdanvladmihai Data 3 aprilie 2021 12:40:45
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1 kb
#include <bits/stdc++.h>

using namespace std;

#define debug(x) cerr << #x << " = " << x << "\n";

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

const int max_n = (int)2e6 + 5;

char s[max_n], p[max_n];

int lps[max_n];

vector<int> ans;

int main() {
  in >> (p + 1) >> (s + 1);
  lps[0] = lps[1] = 0;
  s[0] = p[0] = '\0';
  int n = strlen(p + 1);
  int m = strlen(s + 1);
  for (int i = 2; i <= n; i++) {
    int k = lps[i - 1];
    while (k > 0 && p[k + 1] != p[i]) {
      k = lps[k];
    }
    if (p[k + 1] == p[i]) {
      lps[i] = k + 1;
    } else {
      lps[i] = 0;
    }
  }
  int k = 0;
  for (int i = 1; i <= m; i++) {
    while (k > 0 && p[k + 1] != s[i]) {
      k = lps[k];
    }
    if (p[k + 1] == s[i]) {
      k++;
    } else {
      k = 0;
    }
    if (k == n) {
      ans.push_back(i - n);
    }
  }
  out << (int)ans.size() << "\n";
  for (int i = 0; i < min(1000, (int)ans.size()); i++) {
    out << ans[i] << " ";
  }
  return 0;
}