Construction des Tableaux de Préfixes (Suffix Array) par Doublage

Un tableau de préfixes (Suffix Array), noté sa, est un tableau où sa[i] représente la position de départ du i-ème suffixe par ordre lexicographique. Le tableau rk, quant à lui, stocke le rang de chaque suffixe : rk[i] est le rang du suffixe commençant à la position i. La construction par doublage exploite les rangs des préfixes de longueur w pour déterminer les rangs des préfixes de longueur 2*w.

Lors de la comparaison de deux suffixes pour les trier, on utilise leurs rangs actuels comme clés de tri. Le rang du préfixe de longueur w constitue la première clé, et le rang du préfixe suivant de longueur w (qui forme la seconde moitié du préfixe de longueur 2*w) constitue la seconde clé. Un tri par comptage sur la seconde clé, suivi d'un tri par comptage sur la première clé, permet d'ordonner efficacement les suffixes. Le tri par comptage étant stable, si les premières moitiés sont identiques, l'ordre relatif est préservé, assurant ainsi le tri correct basé sur la seconde moitié.

Bien que les rangs finaux sa et rk soient uniques, des égalités de rangs peuvent survenir pendant le processus de construction.

Optimisations Courantes

• Si la plage des valeurs de rangs atteint n (la longueur de la chaîne), cela signifie que tous les suffixes sont déjà triés, et l'algorithme peut se terminer prématurément.
• L'étape de tri sur la seconde clé peut être optimisée en plaçant d'abord les suffixes dont la seconde moitié est incomplète, puis en conservant l'ordre relatif des suffixes triés à l'étape précédente pour les suffixes dont la seconde moitié est complète.

Exemple de Code pour le Tri des Préfixes

#include<bits/stdc++.h>
using namespace std;
const int MAX_N = 2e6 + 100;
string input_string;
int n, value_range, count_array[MAX_N], sa[MAX_N], rank_array[MAX_N], temp_rank[MAX_N], temp_sa[MAX_N];

signed main() {
    cin >> input_string;
    n = input_string.size();
    input_string = " " + input_string; // Indexation 1-based
    value_range = 256; // Initial value range for ASCII characters

    // Initial sort based on the first character
    for (int i = 1; i <= n; ++i) {
        count_array[rank_array[i] = input_string[i]]++;
    }
    for (int i = 1; i <= value_range; ++i) {
        count_array[i] += count_array[i - 1];
    }
    for (int i = n; i >= 1; --i) {
        sa[count_array[input_string[i]]--] = i;
    }

    // Assign initial ranks
    int current_rank = 0;
    for (int i = 1; i <= n; ++i) {
        if (input_string[sa[i]] != input_string[sa[i - 1]]) {
            current_rank++;
        }
        rank_array[sa[i]] = current_rank;
    }

    // Doubling process
    for (int current_len = 1; current_len < n; current_len <<= 1) {
        if (value_range == n) { // Optimization: early exit if already sorted
            break;
        }

        // Sort by the second half (rank_array[i + current_len])
        for (int i = 0; i <= value_range; ++i) {
            count_array[i] = 0;
        }
        for (int i = 1; i <= n; ++i) {
            temp_sa[i] = sa[i]; // Store current sa
        }
        for (int i = 1; i <= n; ++i) {
            count_array[rank_array[temp_sa[i] + current_len]]++;
        }
        for (int i = 1; i <= value_range; ++i) {
            count_array[i] += count_array[i - 1];
        }
        for (int i = n; i >= 1; --i) {
            temp_sa[count_array[rank_array[sa[i] + current_len]]--] = sa[i];
        }
        for (int i = 1; i <= n; ++i) {
            sa[i] = temp_sa[i];
        }

        // Sort by the first half (rank_array[i])
        for (int i = 0; i <= value_range; ++i) {
            count_array[i] = 0;
        }
        for (int i = 1; i <= n; ++i) {
            temp_sa[i] = sa[i]; // Store current sa
        }
        for (int i = 1; i <= n; ++i) {
            count_array[rank_array[temp_sa[i]]]++;
        }
        for (int i = 1; i <= value_range; ++i) {
            count_array[i] += count_array[i - 1];
        }
        for (int i = n; i >= 1; --i) {
            temp_sa[count_array[rank_array[sa[i]]]--] = sa[i];
        }
        for (int i = 1; i <= n; ++i) {
            sa[i] = temp_sa[i];
            temp_rank[i] = rank_array[i]; // Store previous ranks for comparison
        }

        // Re-assign ranks based on pairs
        current_rank = 0;
        for (int i = 1; i <= n; ++i) {
            if (temp_rank[sa[i]] != temp_rank[sa[i - 1]] || temp_rank[sa[i] + current_len] != temp_rank[sa[i - 1] + current_len]) {
                current_rank++;
            }
            rank_array[sa[i]] = current_rank;
        }
        value_range = current_rank; // Update the value range
    }

    // Output the final suffix array
    for (int i = 1; i <= n; ++i) {
        cout << sa[i] << ' ';
    }
    cout << endl;
    return 0;
}

Construction de l'Automate de Sous-chaînes (Suffix Automaton - SAM)

Le SAM est une représentation compacte de tous les suffixes d'une chaîne, similaire à un automate AC mais optimisé pour les suffixes. Chaque nœud du SAM représente un ensemble de sous-chaînes partageant le même ensemble de positions finales d'occurrence (endpos). Les nœuds sont partitionnés selon ces ensembles endpos.

Dans un SAM, fa[i] pointe vers le nœud représentant le plus long suffixe de l'ensemble endpos de i qui n'est pas dans le même ensemble endpos. Ces liens fa forment une structure arborescente. L'enesmble endpos de chaque nœud inclut strictement celui de ses enfants, et la longueur maximale des sous-chaînes représentées par un nœud est inférieure à celle de ses descendants. Les transitions ch[u][c] indiquent le nœud atteint depuis le nœud u en suivant le caractère c.

La longueur maximale des sous-chaînes représentées par un nœud, notée len, est utilisée pour déduire l'ensemble endpos.

Construction Incrémentale du SAM

La construction incrémentale ajoute un caractère c à la chaîne existante. Cela affecte les ensembles endpos de toutes les sous-chaînes se terminant par ce nouveau caractère. Les nouveaux suffixes qui n'existaient pas auparavant sont représentés par un nouveau nœud (nw). Pour les suffixes existants, la mise à jour commence par le nœud du plus long suffixe.

Le processus implique de remonter depuis le nœud las (dernier nœud ajouté) via les liens fa jusqu'à trouver un nœud p ayant une transition pour le caractère c menant au nœud q (ch[p][c] == q). On examine alors si l'ensemble endpos de q doit être modifié.

• Si len[p] + 1 == len[q], le nœud q représente déjà le plus long suffixe pertinent. On établit simplement fa[nw] = q.
• Si len[p] + 1 != len[q], les sous-chaînes de q dont la longueur est inférieure ou égale à len[p] + 1 voient leur ensemble endpos modifié. Les sous-chaînes plus longues ne sont pas affectées. Il faut donc cloner le nœud q en un nouveau nœud nq pour représenter le plus long suffixe. Les transitions de nq sont héritées de q. L'ensemble endpos de nq inclut la nouvelle position |s| + 1. Dans ce cas, on établit fa[q] = nq et fa[nw] = nq, tandis que fa[nq] pointe vers l'ancien fa[q].

Lors de la remontée via les liens fa, il est nécessaire de gérer correctement les transitions.

Exemple de Code pour la Construction du SAM

#include<bits/stdc++.h>
using namespace std;
const int MAX_NODES = 2e6 + 10;
char input_buffer[MAX_NODES];
int last_state = 1; // Initialize with root node

struct SuffixAutomaton {
    int children[MAX_NODES][26];
    int parent_link[MAX_NODES];
    int max_len[MAX_NODES];
    int occurrence_count[MAX_NODES]; // Stores occurrences for original string
    int topological_degree[MAX_NODES]; // For topological sort
    int node_count = 1; // Start with one node (root)

    void insert_char(char c) {
        int new_node = ++node_count;
        max_len[new_node] = max_len[last_state] + 1;
        occurrence_count[new_node] = 1; // Mark as occurring once initially

        int p = last_state;
        // Traverse up the suffix links until a transition for 'c' is found or root is reached
        while (p > 0 && children[p][c - 'a'] == 0) {
            children[p][c - 'a'] = new_node;
            p = parent_link[p];
        }

        if (p == 0) {
            // No transition found, link new_node to root
            parent_link[new_node] = 1;
            topological_degree[1]++;
        } else {
            int q = children[p][c - 'a'];
            if (max_len[p] + 1 == max_len[q]) {
                // Case 1: Direct link is sufficient
                parent_link[new_node] = q;
                topological_degree[q]++;
            } else {
                // Case 2: Need to split node 'q'
                int cloned_node = ++node_count;
                max_len[cloned_node] = max_len[p] + 1;
                parent_link[cloned_node] = parent_link[q];
                parent_link[q] = cloned_node;
                parent_link[new_node] = cloned_node;
                topological_degree[cloned_node] += 2; // Split increases degree for parent and itself

                // Copy transitions from 'q' to 'cloned_node'
                for (int i = 0; i < 26; ++i) {
                    children[cloned_node][i] = children[q][i];
                }

                // Redirect transitions pointing to 'q' to 'cloned_node'
                int current_ancestor = p;
                while (current_ancestor > 0) {
                    if (children[current_ancestor][c - 'a'] == q) {
                        children[current_ancestor][c - 'a'] = cloned_node;
                    }
                    current_ancestor = parent_link[current_ancestor];
                }
            }
        }
        last_state = new_node; // Update last state
    }

    void query_max_occurrences() {
        queue<int> q;
        long long max_product = 0;

        // Initialize queue with nodes having zero in-degree
        for (int i = 1; i <= node_count; ++i) {
            if (topological_degree[i] == 0) {
                q.push(i);
            }
        }

        // Process nodes in topological order
        while (!q.empty()) {
            int u = q.front();
            q.pop();

            int v = parent_link[u];
            // Propagate occurrence counts up the suffix link tree
            occurrence_count[v] += occurrence_count[u];

            // Calculate max product of (occurrence_count * max_len) if not a state created by splitting
            // and if it's not the root
            if (occurrence_count[u] != 1) { // Check if it's a meaningful state
                max_product = max(max_product, 1LL * occurrence_count[u] * max_len[u]);
            }

            // Decrease in-degree of the parent and add to queue if it becomes zero
            topological_degree[v]--;
            if (topological_degree[v] == 0) {
                q.push(v);
            }
        }
        cout << max_product << endl;
    }
} SAM;

signed main() {
    scanf("%s", input_buffer + 1); // Read string with 1-based indexing
    int n = strlen(input_buffer + 1);
    for (int i = 1; i <= n; ++i) {
        SAM.insert_char(input_buffer[i]);
    }
    SAM.query_max_occurrences();
    return 0;
}