432D - Prefixes and Suffixes - CodeForces Solution

#include <bits/stdc++.h>

using namespace std;
const int N_MAX = 1e5;


/// Observatii si comentarii :
/// In primul rand trebuie sa aflam prefixele care respecta conditia din enunt
/// Cel mai lung dintre ele este chiar raspunsul dat de KMP --> LPS[n - 1]
/// Fie Pk lungimea prefixului curent. Atunci urmatorul cel mai lung prefix va fi cel de lungime LPS[Pk - 1]
/// Nota : Sirul de lungime n se adauga la inceput cu frecventa 1
/// In al doilea rand trebuie sa aflam frecventele acestor prefixe
/// Ne propunem sa aflam pentru o pozitie i sa aflam ce prefixe se termina pe acea pozitie
/// In aceeasi maniera, cel mai lung dintre ele este LPS[i]
/// Fie Pk prefixului curent. Atunci urmatorul cel mai lung prefix va fi cel de lungime LPS[Pk - 1]
/// Astfel pentru fiecare pozitie i = 0..n - 1 se formeaza un sir de prefixe care apar
/// Aceste siruri sunt descrescatoare si urmeaza regula prefix --> LPS[prefix - 1]
/// Momentan noi cunoastem doar frecventa "sefilor" de sir (primului numar din sir)
/// Pentru a frecventa lui LPS[prefix - 1] trebuie mai intai sa aflam frecventa lui prefix
/// Asadar ar fi minunat daca am gasi o sortare topologica a acestor prefixe
/// => graful format de aceste prefix trebuie sa fie unul directionat si aciclic
/// cunoastem ca este directionat si este chiar si aciclic deoarece sirurile sunt descrescatoare
/// Altfel spus, nu ne putem intoarce de la ceva mic la ceva mare
/// Asadar formam graful, il sortam topologic iar frecv[LPS[prefix - 1]] += frecv[prefix]
/// deoarece unde apare prefix sigur apare si LPS[prefix - 1]

int LPS[1 + N_MAX];
int frecv[1 + N_MAX];

vector<int> DAG[1 + N_MAX];
void KMP (string input) {
   int n = input.size (); LPS[0] = 0;

   int k = 0; /// curr lps
   for (int i = 1; i < n; i ++) {
      while (k > 0 && input[i] != input[k])
         k = LPS[k - 1];
      if (input[i] == input[k])
        k ++;

      LPS[i] = k;

      frecv[k] ++;
      if (frecv[k] == 1) /// adaosul prefix -- LPS[prefix - 1] trebuie sa se intample exact o data
        DAG[k].push_back (LPS[k - 1]);
   }
}


vector<int> topoSort;
bool visited[1 + N_MAX];

void dfs (int root) {
   visited[root] = true;
   for (int node : DAG[root])
      if (!visited[node])
        dfs (node);
   topoSort.push_back (root);
}

struct defAnswer {
   int preff, counter;
};

int main()
{
   string input; cin >> input;
   KMP (input);

   int n = input.size ();
   for (int preff = 0; preff < n; preff ++)
      if (!visited[preff])
        dfs (preff);

   reverse (topoSort.begin (), topoSort.end ());

   for (int node : topoSort) {
      for (int u : DAG[node])
         frecv[u] += frecv[node];
   }
   vector<defAnswer> answer;
   answer.push_back ({n, 1});

   int k = LPS[n - 1];
   while (k > 0) {
      answer.push_back ({k, 1 + frecv[k]}); /// adunam 1 pentru a considera si prefixul in sine care NU este considerat de KMP
      k = LPS[k - 1];
   }
   reverse (answer.begin (), answer.end ());

   cout << answer.size () << "\n";
   for (defAnswer obj : answer) {
      cout << obj.preff << " " << obj.counter;
      cout << "\n";
   }
    return 0;
}