Cod sursa(job #2839126)

Utilizator TeodorLuchianovTeo Luchianov TeodorLuchianov Data 25 ianuarie 2022 12:43:34
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.9 kb
#include <fstream>
#include <vector>
#include <iostream>

using namespace std;

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

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

string s;

vector <int> sol;

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{
      int q = dp[i-1];
      while(q != 0 && s[q] != s[i]){
        q = dp[q - 1];
      }
      if(s[q] == s[i]){
        q++;
      }
      dp[i] = q;
    }
    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;
}