Cod sursa(job #2929206)

Utilizator raresgherasaRares Gherasa raresgherasa Data 25 octombrie 2022 10:57:19
Problema Potrivirea sirurilor Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.12 kb
#include <bits/stdc++.h>

using namespace std;

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

const int NM = 2e6 + 2;

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

void precalc(char s[], int n){
  a[0] = 0;
  int index = 0;
  for (int i = 1; i < n;){
    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(t, m);
  for (int i = 0, index = 0; i < m;){
    if (t[i] == s[index]){///match
      if (index == n - 1){
        ans += 1;
        if (int(v.size()) < 1000){
          v.push_back(i - n + 1);
        }
        index = a[index - 1];
      }
      else{
        index += 1;
        i += 1;
      }
    }
    else{
      if (index != 0){
        index = a[index - 1];
      }
      else{
        i += 1;
      }
    }
  }
  fout << ans << '\n';
  for (int x : v){
    fout << x << " ";
  }
}