Cod sursa(job #2568303)

Utilizator AlexNeaguAlexandru AlexNeagu Data 3 martie 2020 21:59:16
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.77 kb
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long ll;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
const int N = 4000005;
string s;
char c;
vector < int > ans;
int pi[N];
int n;
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  in >> s;
  n = s.size();
  s += '#';
  while(in >> c) {
    s += c;
  }
  for (int i = 1; i < s.size(); i++) {
    int len = pi[i - 1];
    while(len > 0 && s[len] != s[i]) {
      len = pi[len - 1];
    }
    if (s[len] == s[i]) {
      len++;
    }
    pi[i] = len;
    if (pi[i] == n && ans.size() < 1000) {
      ans.push_back(i - 2 * n);
    }
  }
  out << ans.size() << "\n";
  for (auto it : ans) {
    out << it << " ";
  }
  return 0;
}