Étant donné deux chaînes de caractères source et cible, le défi consiste à déterminer combien de caractères de la chaîne cible peuvent être trouvés dans le même ordre au sein de la chaîne source. En d'autres termes, il faut identifier si la chaîne cible constitue une sous-séquence de source et compter le nombre de correspondances trouvées. Les données d'entrée proviennent du fichier entree.txt et le résultat est записуется dans le fichier sortie.txt.

Format d'entrée

Le fichier entree.txt contient deux lignes distinctes. La première ligne représente la chaîne source et la seconde ligne représente la chaîne cible. Chaque chaîne est composée de caractères imprimables et leur longueur ne dépasse pas 1000 caractères.

Format de sortie

Le fichier sortie.txt contient un entier unique correspondant au nombre de caractères de la chaîne cible qui ont été trouvés dans le même ordre au sein de la chaîne source.

Exemple illustratif

Considérons les chaînes suivantes :

source: abcde
cible: ace

Le résultat obtenu est :

3

Explication de l'exemple

Les caractères a, c et e de la chaîne cible apparaissent dans le même ordre au sein de la chaîne source. Par conséquent, le nombre de correspondances est égal à 3.

Analyse algorithmique

L'algorithme repose sur une approche par balayage séquentiel. On parcourt chaque caractère de la chaîne cible et on cherche sa correspondance dans la chaîne source en commençant à partir de la position où la recherche précédente s'est terminée. Cette technique garantit que l'ordre des caractères est respecté.

Implémentation

#include <bits/stdc++.h>
using namespace std;

// Tableaux de caractères pour stocker les chaînes d'entrée
char source[1005], cible[1005];

// Variables pour la gestion de l'algorithme
int positionRecherche, longueurSource, longueurCible, compteur;
int indexSource, indexCible;

int main(){
    // Redirection des flux d'entrée et de sortie vers les fichiers
    freopen("entree.txt", "r", stdin);
    freopen("sortie.txt", "w", stdout);
    
    // Lecture des deux chaînes de caractères
    cin >> source >> cible;
    
    // Calcul des longueurs des chaînes
    longueurSource = strlen(source);
    longueurCible = strlen(cible);
    
    // Initialisation du compteur de correspondances
    compteur = 0;
    
    // Définition du point de départ pour la première recherche
    positionRecherche = 0;
    
    // Parcours de chaque caractère de la chaîne cible
    for(indexCible = 0; indexCible < longueurCible; indexCible++){
        // Recherche du caractère actuel dans la chaîne source
        for(indexSource = positionRecherche; indexSource < longueurSource; indexSource++){
            // Vérification de la correspondance des caractères
            if(cible[indexCible] == source[indexSource]){
                // Mise à jour de la position pour la prochaine recherche
                positionRecherche = indexSource + 1;
                // Incrémentation du compteur de correspondances
                compteur++;
                // Arrêt de la recherche une fois le caractère trouvé
                break;
            }
        }
        
        // Sortie anticipée si aucun caractère correspondant n'est trouvé
        if(indexSource == longueurSource){
            break;
        }
    }
    
    // Affichage du résultat final
    cout << compteur;
    return 0;
}

Déroulement de l'exécution

L'exécution du programme se déroule en plusieurs phases distinctes. Premièrement, les flux d'entrée et de sortie sont redirigés vers les ficihers spécifiés à l'aide de la fonction freopen. Ensuite, les deux chaînes de caractères sont lues depuis le fichier d'entrée et leurs longueurs respectives sont calculées.

La phase principale de l'algorithme consiste à parcourir la chaîne cible caractère par caractère. Pour chaque caractère, on effectue une recherche dans la chaîne source en commençant à la position mémorisée lors de la recherche précédente. Lorsqu'une correspondance est trouvée, la position de recherche est mise à jour pour continuer après le caractère trouvé, et le compteur de correspondances est incrémenté.

Si la recherche dans la chaîne source épuisée toutes les positions possibles sans trouver le caractère actuel de cible, l'algorithme met fin prématurément à la boucle principale, car aucun caractère suivant ne pourra être trouvé.

Analyse de la complexité

Du point de vue de la complexité temporelle, l'algorithme présente une caractéristique de O(m × n), où m représente la longueur de la chaîne cible et n représente la longueur de la chaîne source. Dans le pire des cas, pour chaque caractère de cible, l'algorithme doit parcourir l'intégralité de source.

Concernant la complexité spatiale, l'algorithme utilise O(m + n) d'espace, principalement pour le stockage des deux chaînes de caractères. Les variables supplémantaires occupent un espace constant et négligeable.

Cette appproche, bien que simple, offre une solution directe et compréhensible pour le problème de comptage des sous-séquences. Pour des chaînes de longueur maximale de 1000 caractères, les performances restent tout à fait acceptables dans un contexte de compétition.