Cod sursa(job #2924007)

Utilizator raresgherasaRares Gherasa raresgherasa Data 22 septembrie 2022 20:47:55
Problema Potrivirea sirurilor Scor 18
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.15 kb
#include <bits/stdc++.h>

using namespace std;

const string fisier = "strmatch";

ifstream fin (fisier + ".in");
ofstream fout (fisier + ".out");

const int NM = 2e6 + 5;

char s[NM], t[NM];
int n, m, a[NM];
vector<int>ans;

void precalc (char s[]){
  int index = 0;
  a[0] = 0;
  for (int i = 1; i < n; i++){
    if (s[i] == s[index]){
      index += 1;
      a[i] = index;
      i += 1;
    }
    else{
      if (index != 0){
        index = a[index - 1];
      }
      else{
        a[i] = 0;
        i += 1;
      }
    }
  }
}

int main(){
  fin >> s >> t;
  n = (int)strlen(s);
  m = (int)strlen(t);
  precalc(s);

  int index = 0;
  for (int i = 0; i < m;){
    if (t[i] == s[index]){
      if (index == n - 1){
        ans.push_back(i - n + 1);
        index = a[index - 1];
      }
      else{
        index += 1;
        i += 1;
      }
    }
    else{
      if (index != 0){
        index = a[index - 1];
      }
      else if (index != n){
        i += 1;
      }
    }
  }

  fout << ans.size() << '\n';
  for (int i = 0; i < min(1000, (int)ans.size()); i++){
    fout << ans[i] << " ";
  }
}