Cod sursa(job #2838507)

Utilizator TeodorLuchianovTeo Luchianov TeodorLuchianov Data 23 ianuarie 2022 21:00:42
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.96 kb
#include <fstream>
#include <vector>

using namespace std;

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

int const NMAX = 2e6;
int dp[1 + NMAX];

string s;

vector <int> sol;

bool isEqual(int siz, int lim) {
  for(int i = 0;i < siz;i++){
    if(s[i] != s[lim - siz + i + 1]){
      return false;
    }
  }
  return true;
}

void solve(int ssol){
  int ans = 0;
  dp[0] = 0;
  for(int i = 1;i < s.size();i++){
    if(s[dp[i-1]] == s[i]){
      dp[i] = dp[i-1] + 1;
    }else{
      dp[i] = dp[i-1];
      while(!isEqual(dp[i], i)){
        dp[i]--;
      }
    }
    if(dp[i] >= ssol){
      ans++;
      if(ans <= 1000){
        sol.push_back(i - 2 * ssol);
      }
    }
    //cout << dp[i] << " ";
  }
  out << ans << '\n';
  for(int i = 0;i < sol.size();i++){
    out << sol[i] << ' ';
  }
}

int main() {

  string a, b;
  in >> a >> b;
  a.push_back('#');
  s = a + b;
  solve(a.size() - 1);
  return 0;
}