Cod sursa(job #2905995)

Utilizator vlad.ulmeanu30Ulmeanu Vlad vlad.ulmeanu30 Data 24 mai 2022 18:38:08
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.33 kb
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define pli pair<ll,int>
#define pil pair<int,ll>
#define pll pair<ll,ll>
#define fi first
#define se second
#define inf (INT_MAX/2-1)
#define infl (1LL<<61)
#define vi vector<int>
#define vl vector<ll>
#define pb push_back
#define sz(a) ((int)(a).size())
#define all(a) begin(a),end(a)
#define y0 y5656
#define y1 y7878
#define aaa system("pause");
#define dbg(x) std::cerr<<(#x)<<": "<<(x)<<'\n',aaa
#define dbga(x,n) std::cerr<<(#x)<<"[]: ";for(int _=0;_<n;_++)std::cerr<<x[_]<<' ';std::cerr<<'\n',aaa
#define dbgs(x) std::cerr<<(#x)<<"[stl]: ";for(auto _:x)std::cerr<<_<<' ';std::cerr<<'\n',aaa
#define dbgp(x) std::cerr<<(#x)<<": "<<x.fi<<' '<<x.se<<'\n',aaa
#define dbgsp(x) std::cerr<<(#x)<<"[stl pair]:\n";for(auto _:x)std::cerr<<_.fi<<' '<<_.se<<'\n';aaa
#define maxn 2000000

using namespace std;

string s, t;
int lps[maxn+5]; ///peste t.

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

  fin >> t >> s;
  int m = sz(t), n = sz(s);

  s = " " + s;
  t = " " + t;

  lps[0] = lps[1] = 0;

  int i, j, z;

  ///(t) construire cel mai lung prefix (diferit de tot sirul) care este si sufix.
  for (i = 2; i <= m; i++) {
    lps[i] = 0;
    j = i;
    while (j > 0) {
      if (t[lps[j-1] + 1] == t[i]) {
        lps[i] = lps[j-1] + 1;
        break;
      }
      j = lps[j-1];
    }
  }

  vi sol;
  ///pp ca am T[s..s+x-1] = P[0..x-1], nu mai merge inca un ch, adica T[s..s+x] = P[0..x].
  ///vreau s' minim, s+x > s' > s ai T[s'..s'+k-1] = P[0..k-1] SI s+x = s'+k.
  ///s' > s <=> k < x. vreau s' minim adica profit cat mai mult de bucata busita s..s+x-1, deci k maxim.
  ///T[s..s+x-1] = P[0..x-1], T[s'..s'+k-1] = P[0..k-1], s' > s => T[s..s+k-1] = P[0..k-1].
  ///deci T[s..s+k-1] = T[s'..s'+k-1]. adica k = lps[x].

  i = 1;
  j = 1;
  while (i <= n-m+1) {
    if (s[i+j-1] == t[j]) {
      j++;
      if (j > m) {
        sol.pb(i);
        i = i+m - lps[m];
        j = lps[m] + 1;
      }
    } else {
      if (j == 1) {
        i++;
      } else {
        i = i+j-1 - lps[j-1];
        j = lps[j-1] + 1;
      }
    }
  }

  fout << sz(sol) << '\n';
  sol.resize(min(sz(sol), 1000));
  for (int x: sol) fout << x-1 << ' ';

  fin.close();
  fout.close();

  return 0;
}