main.cpp

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

// ==========================================
// 1. GLOBAL CONSTANTS (Terminal Colors)
// ==========================================
const string RESET = "\033[0m";
const string RED = "\033[31m";
const string GREEN = "\033[32m";
const string YELLOW = "\033[33m";


// Calculates the minimum operations required (Pure DP)
int calculateMinOperations(int i, int j, const string& word1, const string& word2, vector<vector<int>>& memo);

// Recursively reconstructs the path, returns the colored diff, and logs the steps
string reconstructPath(int i, int j, const string& word1, const string& word2, vector<vector<int>>& memo, vector<string>& stepLog);

// Manages the state, calls the functions, and handles all Console I/O
void runTextComparisonSystem(const string& oldText, const string& newText);

int calculateMinOperations(int i, int j, const string& word1, const string& word2, vector<vector<int>>& memo) {
    // Base cases
    if (i < 0) return j + 1;
    if (j < 0) return i + 1;

    int &ret = memo[i][j];
    if (ret != -1) return ret;

    ret = 1e9; // Infinity

    // Match State
    if (word1[i] == word2[j]) {
        ret = min(ret, calculateMinOperations(i - 1, j - 1, word1, word2, memo));
    }

    // Delete, Insert, Replace States
    ret = min(ret, 1 + calculateMinOperations(i - 1, j, word1, word2, memo));
    ret = min(ret, 1 + calculateMinOperations(i, j - 1, word1, word2, memo));
    ret = min(ret, 1 + calculateMinOperations(i - 1, j - 1, word1, word2, memo));

    return ret;
}

string reconstructPath(int i, int j, const string& word1, const string& word2, vector<vector<int>>& memo, vector<string>& stepLog) {
    // Base Case 1: Insert remaining characters
    if (i < 0) {
        string diffResult = "";
        for (int k = 0; k <= j; ++k) {
            stepLog.push_back(GREEN + "INSERT " + to_string(k + 1) + " (" + word2[k] + ")" + RESET);
            diffResult += GREEN + word2[k] + RESET;
        }
        return diffResult;
    }

    // Base Case 2: Delete remaining characters
    if (j < 0) {
        string diffResult = "";
        for (int k = 0; k <= i; ++k) {
            stepLog.push_back(RED + "DELETE " + to_string(k + 1) + " (" + word1[k] + ")" + RESET);
            diffResult += RED + word1[k] + RESET;
        }
        return diffResult;
    }

    int ret = memo[i][j];

    // Backtrack 1: Match
    if (word1[i] == word2[j] && ret == calculateMinOperations(i - 1, j - 1, word1, word2, memo)) {
        string previousDiff = reconstructPath(i - 1, j - 1, word1, word2, memo, stepLog);
        return previousDiff + word1[i];
    }

    // Backtrack 2: Delete
    if (ret == 1 + calculateMinOperations(i - 1, j, word1, word2, memo)) {
        string previousDiff = reconstructPath(i - 1, j, word1, word2, memo, stepLog);
        stepLog.push_back(RED + "DELETE " + to_string(i + 1) + " (" + word1[i] + ")" + RESET);
        return previousDiff + RED + word1[i] + RESET;
    }

    // Backtrack 3: Insert
    if (ret == 1 + calculateMinOperations(i, j - 1, word1, word2, memo)) {
        string previousDiff = reconstructPath(i, j - 1, word1, word2, memo, stepLog);
        stepLog.push_back(GREEN + "INSERT " + to_string(j + 1) + " (" + word2[j] + ")" + RESET);
        return previousDiff + GREEN + word2[j] + RESET;
    }

    // Backtrack 4: Replace
    if (ret == 1 + calculateMinOperations(i - 1, j - 1, word1, word2, memo)) {
        string previousDiff = reconstructPath(i - 1, j - 1, word1, word2, memo, stepLog);
        stepLog.push_back(YELLOW + "REPLACE " + to_string(j + 1) + " (" + word2[j] + ")" + RESET);
        return previousDiff + YELLOW + word2[j] + RESET;
    }

    return "";
}
void runTextComparisonSystem(const string& oldText, const string& newText) {
    int n = oldText.size();
    int m = newText.size();

    // State Initialization
    vector<vector<int>> memo(n, vector<int>(m, -1));
    vector<string> stepLog; // Holds the step-by-step instructions

    cout << "====================================\n";
    cout << "Original Text : " << oldText << "\n";
    cout << "Modified Text : " << newText << "\n";
    cout << "====================================\n";

    // Step 1: Execute Pure DP Function
    int totalOperations = calculateMinOperations(n - 1, m - 1, oldText, newText, memo);
    cout << "Total Operations Needed: " << totalOperations << '\n';
    cout << "====================================\n\n";

    // Step 2: Execute Path Reconstruction (Functional state passing)
    string finalVisualDiff = reconstructPath(n - 1, m - 1, oldText, newText, memo, stepLog);

    // Step 3: Print the accumulated Step-by-Step Log
    cout << "--- Step-by-Step Operations ---\n";
    for (const string& step : stepLog) {
        cout << step << '\n';
    }

    // Step 4: Print the Final Visual Diff
    cout << "\n--- Final Visual Diff ---\n";
    cout << finalVisualDiff << '\n';
    cout << "====================================\n\n";
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
   // Define Inputs
    string oldText = "Dynamic Progamming is hard.";
    string newText = "Dynamic Programming is fun!";

    // Run System
    runTextComparisonSystem(oldText, newText);

    return 0;
}