Cod sursa(job #3216231)

Utilizator dorufDoru Floare doruf Data 15 martie 2024 18:42:58
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.9 kb
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
#define eb emplace_back
using ll = long long;
using ld = long double;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string str,pat;
vi kmp() {
  int n = str.size();
  vi p(n);
  for (int i = 1; i < n; ++i) {
    int j = p[i - 1];
    while(j>0 && str[i] != str[j])
      j = p[j-1];
    if (str[i]==str[j])++j;
    p[i]=j;
  }
  return p;
}

int main() {
  ios_base::sync_with_stdio(false);
  fin.tie(0);
  fout.tie(0);

  fin >> pat >> str;
  str = pat + "$" + str;
  vector<int> pref = kmp();

  vector<int> ans;
  int cnt = 0;
  for (int i = pat.size() + 1; i < str.size(); ++i)
    if (pref[i] == pat.size()) {
      ++cnt;
      if ((int)ans.size() < 1000)
        ans.emplace_back(i - pat.size() - 1);
    }
  fout << cnt << '\n';
  for (auto i : ans)
    fout << i-pat.size()+1 << ' ';
}