الخوارزميات المتقدمة

تنفيذ الخوارزمية بلغة Python:

def coin_change_greedy(coins, amount):
    """
    حل مسألة تغيير العملات باستخدام الخوارزمية الطماعة
    
    المعطيات:
    coins -- قائمة بفئات العملات المتاحة
    amount -- المبلغ المطلوب تغييره
    
    إرجاع:
    قائمة بالعملات المستخدمة
    """
    # ترتيب العملات تنازليًا
    coins.sort(reverse=True)
    
    result = []
    remaining = amount
    
    # تطبيق الاستراتيجية الطماعة
    for coin in coins:
        # استخدام أكبر عدد ممكن من العملة الحالية
        while remaining >= coin:
            result.append(coin)
            remaining -= coin
    
    # التحقق من أننا استطعنا تغيير المبلغ بالكامل
    if remaining == 0:
        return result
    else:
        return "لا يمكن إيجاد الحل باستخدام فئات العملات المتاحة"

# مثال للاستخدام
coins = [1, 5, 10, 25, 100]  # فئات العملات: 1 سنت، 5 سنت، 10 سنت، 25 سنت، 1 دولار
amount = 289

result = coin_change_greedy(coins, amount)
print(f"العملات المستخدمة: {result}")
print(f"عدد العملات: {len(result)}")

ملاحظة: الخوارزمية الطماعة لا تعطي دائمًا الحل الأمثل لمسألة تغيير العملات. على سبيل المثال، إذا كانت فئات العملات هي [1, 3, 4] والمبلغ المطلوب هو 6، فالخوارزمية الطماعة ستختار [4, 1, 1] (3 عملات)، بينما الحل الأمثل هو [3, 3] (2 عملات).

تنفيذ الخوارزمية بلغة Java:

import java.util.*;

class Activity {
    int start, finish;
    
    public Activity(int start, int finish) {
        this.start = start;
        this.finish = finish;
    }
}

public class ActivitySelection {
    // دالة لاختيار أكبر عدد ممكن من الأنشطة المتوافقة
    public static List<Activity> selectActivities(Activity[] activities) {
        // ترتيب الأنشطة حسب وقت الانتهاء
        Arrays.sort(activities, (a, b) -> a.finish - b.finish);
        
        List<Activity> selectedActivities = new ArrayList<>();
        
        // اختيار النشاط الأول دائمًا
        selectedActivities.add(activities[0]);
        
        // آخر نشاط تم اختياره
        int lastSelected = 0;
        
        // اختيار باقي الأنشطة
        for (int i = 1; i < activities.length; i++) {
            // إذا بدأ هذا النشاط بعد انتهاء آخر نشاط تم اختياره
            if (activities[i].start >= activities[lastSelected].finish) {
                selectedActivities.add(activities[i]);
                lastSelected = i;
            }
        }
        
        return selectedActivities;
    }
    
    public static void main(String[] args) {
        // تعريف مجموعة من الأنشطة بأوقات البدء والانتهاء
        Activity[] activities = {
            new Activity(1, 3),
            new Activity(2, 5),
            new Activity(4, 7),
            new Activity(1, 8),
            new Activity(5, 9),
            new Activity(8, 10),
            new Activity(9, 11),
            new Activity(11, 14),
            new Activity(13, 16)
        };
        
        // اختيار الأنشطة المتوافقة
        List<Activity> selected = selectActivities(activities);
        
        // طباعة الأنشطة المختارة
        System.out.println("الأنشطة المختارة:");
        for (Activity activity : selected) {
            System.out.println("بداية: " + activity.start + ", نهاية: " + activity.finish);
        }
        System.out.println("عدد الأنشطة المختارة: " + selected.size());
    }
}

تنفيذ الخوارزمية بلغة C++:

#include <iostream>
#include <vector>
using namespace std;

class NQueens {
private:
    int n;
    vector<vector<string>> solutions;
    
    // التحقق مما إذا كان من الآمن وضع ملكة في الموقع المحدد
    bool isSafe(vector<string>& board, int row, int col) {
        // التحقق من العمود
        for (int i = 0; i < row; i++) {
            if (board[i][col] == 'Q') {
                return false;
            }
        }
        
        // التحقق من القطر الرئيسي (الشمال الغربي)
        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
            if (board[i][j] == 'Q') {
                return false;
            }
        }
        
        // التحقق من القطر الثانوي (الشمال الشرقي)
        for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
            if (board[i][j] == 'Q') {
                return false;
            }
        }
        
        return true;
    }
    
    // حل المسألة بالتراجع
    void solve(vector<string>& board, int row) {
        // تم العثور على حل
        if (row == n) {
            solutions.push_back(board);
            return;
        }
        
        // تجربة وضع ملكة في كل عمود من هذا الصف
        for (int col = 0; col < n; col++) {
            if (isSafe(board, row, col)) {
                // وضع ملكة
                board[row][col] = 'Q';
                
                // الانتقال إلى الصف التالي
                solve(board, row + 1);
                
                // التراجع
                board[row][col] = '.';
            }
        }
    }
    
public:
    vector<vector<string>> solveNQueens(int n) {
        this->n = n;
        solutions.clear();
        
        // إنشاء رقعة شطرنج فارغة
        vector<string> board(n, string(n, '.'));
        
        // حل المسألة بدءًا من الصف 0
        solve(board, 0);
        
        return solutions;
    }
    
    void printSolution(const vector<string>& solution) {
        for (const string& row : solution) {
            for (char cell : row) {
                cout << (cell == 'Q' ? "Q " : ". ");
            }
            cout << endl;
        }
        cout << endl;
    }
};

int main() {
    int n = 4; // عدد الملكات
    
    NQueens nQueens;
    vector<vector<string>> solutions = nQueens.solveNQueens(n);
    
    cout << "عدد الحلول: " << solutions.size() << endl;
    cout << "الحلول:" << endl;
    
    for (int i = 0; i < solutions.size(); i++) {
        cout << "الحل " << (i + 1) << ":" << endl;
        nQueens.printSolution(solutions[i]);
    }
    
    return 0;
}

تنفيذ الخوارزمية بلغة Python:

def print_sudoku(grid):
    """طباعة شبكة السودوكو"""
    for i in range(9):
        if i % 3 == 0 and i != 0:
            print("- - - - - - - - - - - -")
        
        for j in range(9):
            if j % 3 == 0 and j != 0:
                print(" | ", end="")
            
            if j == 8:
                print(grid[i][j])
            else:
                print(str(grid[i][j]) + " ", end="")

def find_empty(grid):
    """إيجاد خلية فارغة (تحتوي على 0)"""
    for i in range(9):
        for j in range(9):
            if grid[i][j] == 0:
                return (i, j)  # الصف، العمود
    
    return None  # لا توجد خلايا فارغة

def valid(grid, num, pos):
    """التحقق من صحة وضع الرقم في الموقع المحدد"""
    # التحقق من الصف
    for j in range(9):
        if grid[pos[0]][j] == num and pos[1] != j:
            return False
    
    # التحقق من العمود
    for i in range(9):
        if grid[i][pos[1]] == num and pos[0] != i:
            return False
    
    # التحقق من المربع 3×3
    box_x = pos[0] // 3
    box_y = pos[1] // 3
    
    for i in range(box_x * 3, box_x * 3 + 3):
        for j in range(box_y * 3, box_y * 3 + 3):
            if grid[i][j] == num and (i, j) != pos:
                return False
    
    return True

def solve(grid):
    """حل السودوكو باستخدام التراجع"""
    # البحث عن خلية فارغة
    find = find_empty(grid)
    if not find:
        return True  # تم حل السودوكو
    else:
        row, col = find
    
    # تجربة وضع الأرقام من 1 إلى 9
    for num in range(1, 10):
        # التحقق من صحة وضع الرقم
        if valid(grid, num, (row, col)):
            # وضع الرقم
            grid[row][col] = num
            
            # الاستمرار في الحل
            if solve(grid):
                return True
            
            # التراجع
            grid[row][col] = 0
    
    return False  # لا يمكن حل السودوكو بالتكوين الحالي

# مثال للسودوكو
grid = [
    [5, 3, 0, 0, 7, 0, 0, 0, 0],
    [6, 0, 0, 1, 9, 5, 0, 0, 0],
    [0, 9, 8, 0, 0, 0, 0, 6, 0],
    [8, 0, 0, 0, 6, 0, 0, 0, 3],
    [4, 0, 0, 8, 0, 3, 0, 0, 1],
    [7, 0, 0, 0, 2, 0, 0, 0, 6],
    [0, 6, 0, 0, 0, 0, 2, 8, 0],
    [0, 0, 0, 4, 1, 9, 0, 0, 5],
    [0, 0, 0, 0, 8, 0, 0, 7, 9]
]

print("السودوكو الأصلي:")
print_sudoku(grid)
print("\nحل السودوكو:")
if solve(grid):
    print_sudoku(grid)
else:
    print("لا يمكن حل هذا السودوكو!")

مثال لدالة تجزئة للنصوص:

function hashString(str, tableSize) {
    let hash = 0;
    
    // استخدام خوارزمية djb2
    for (let i = 0; i < str.length; i++) {
        hash = ((hash << 5) + hash) + str.charCodeAt(i); // hash * 33 + char_code
    }
    
    // التأكد من أن الفهرس ضمن حدود الجدول
    return Math.abs(hash) % tableSize;
}

// مثال للاستخدام
const tableSize = 1000;
console.log(hashString("مرحبا", tableSize));
console.log(hashString("عالم", tableSize));

2. التسلسل المغلق (Closed Addressing):

• التسلسل المتصل (Chaining): تخزين جميع العناصر ذات نفس قيمة التجزئة في قائمة متصلة.

class HashTable {
    constructor(size = 53) {
        this.table = new Array(size);
        this.size = size;
    }
    
    // دالة التجزئة
    _hash(key) {
        let total = 0;
        // عدد أولي للحصول على توزيع أفضل
        const PRIME = 31;
        
        // التحويل إلى سلسلة نصية إذا لم تكن كذلك
        const strKey = String(key);
        
        // استخدام أول 100 حرف فقط للمفاتيح الطويلة
        for (let i = 0; i < Math.min(strKey.length, 100); i++) {
            // الحصول على قيمة الحرف
            const char = strKey[i];
            const value = char.charCodeAt(0);
            
            // حساب قيمة التجزئة
            total = (total * PRIME + value) % this.size;
        }
        
        return total;
    }
    
    // إدراج زوج مفتاح/قيمة
    set(key, value) {
        // حساب فهرس المفتاح
        const index = this._hash(key);
        
        // إذا كان الفهرس فارغًا، أنشئ قائمة متصلة (مصفوفة)
        if (!this.table[index]) {
            this.table[index] = [];
        }
        
        // التحقق إذا كان المفتاح موجودًا مسبقًا
        for (let i = 0; i < this.table[index].length; i++) {
            if (this.table[index][i][0] === key) {
                // تحديث القيمة إذا كان المفتاح موجودًا
                this.table[index][i][1] = value;
                return;
            }
        }
        
        // إضافة زوج مفتاح/قيمة جديد
        this.table[index].push([key, value]);
    }
    
    // الحصول على قيمة لمفتاح معين
    get(key) {
        // حساب فهرس المفتاح
        const index = this._hash(key);
        
        // إذا لم يكن هناك عناصر في هذا الفهرس
        if (!this.table[index]) return undefined;
        
        // البحث عن المفتاح في القائمة المتصلة
        for (let i = 0; i < this.table[index].length; i++) {
            if (this.table[index][i][0] === key) {
                return this.table[index][i][1];
            }
        }
        
        // المفتاح غير موجود
        return undefined;
    }
    
    // حذف زوج مفتاح/قيمة
    remove(key) {
        // حساب فهرس المفتاح
        const index = this._hash(key);
        
        // إذا لم يكن هناك عناصر في هذا الفهرس
        if (!this.table[index]) return false;
        
        // البحث عن المفتاح وحذفه
        for (let i = 0; i < this.table[index].length; i++) {
            if (this.table[index][i][0] === key) {
                this.table[index].splice(i, 1);
                return true;
            }
        }
        
        // المفتاح غير موجود
        return false;
    }
}

// مثال للاستخدام
const hashTable = new HashTable();

// إضافة بيانات
hashTable.set("اسم", "أحمد");
hashTable.set("عمر", 30);
hashTable.set("مدينة", "الرياض");

// استرجاع البيانات
console.log(hashTable.get("اسم"));    // أحمد
console.log(hashTable.get("عمر"));    // 30
console.log(hashTable.get("مدينة"));  // الرياض

// حذف بيانات
hashTable.remove("عمر");
console.log(hashTable.get("عمر"));    // undefined

تنفيذ كومة أدنوية (Min Heap) بلغة Python:

class MinHeap:
    def __init__(self):
        """تهيئة كومة أدنوية فارغة."""
        self.heap = []
    
    def parent(self, i):
        """إرجاع فهرس الأب للعنصر في الموقع i."""
        return (i - 1) // 2
    
    def left_child(self, i):
        """إرجاع فهرس الابن الأيسر للعنصر في الموقع i."""
        return 2 * i + 1
    
    def right_child(self, i):
        """إرجاع فهرس الابن الأيمن للعنصر في الموقع i."""
        return 2 * i + 2
    
    def get_min(self):
        """إرجاع العنصر الأدنى دون إزالته."""
        if len(self.heap) == 0:
            return None
        return self.heap[0]
    
    def extract_min(self):
        """إزالة وإرجاع العنصر الأدنى."""
        if len(self.heap) == 0:
            return None
        
        # حفظ العنصر الأدنى
        min_item = self.heap[0]
        
        # نقل آخر عنصر إلى الجذر وإزالة الأخير
        self.heap[0] = self.heap[-1]
        self.heap.pop()
        
        # إعادة ترتيب الكومة
        if len(self.heap) > 0:
            self._sift_down(0)
        
        return min_item
    
    def insert(self, item):
        """إضافة عنصر جديد للكومة."""
        # إضافة العنصر في نهاية الكومة
        self.heap.append(item)
        
        # إعادة ترتيب الكومة (من أسفل إلى أعلى)
        self._sift_up(len(self.heap) - 1)
    
    def _sift_up(self, i):
        """نقل العنصر للأعلى حتى يتحقق شرط الكومة الأدنوية."""
        parent_idx = self.parent(i)
        
        # إذا كان العنصر أصغر من الأب، نبدلهما ونستمر في النقل للأعلى
        if i > 0 and self.heap[i] < self.heap[parent_idx]:
            self.heap[i], self.heap[parent_idx] = self.heap[parent_idx], self.heap[i]
            self._sift_up(parent_idx)
    
    def _sift_down(self, i):
        """نقل العنصر للأسفل حتى يتحقق شرط الكومة الأدنوية."""
        min_idx = i
        left = self.left_child(i)
        right = self.right_child(i)
        
        # إيجاد العنصر الأصغر بين العنصر الحالي والأبناء
        if left < len(self.heap) and self.heap[left] < self.heap[min_idx]:
            min_idx = left
        
        if right < len(self.heap) and self.heap[right] < self.heap[min_idx]:
            min_idx = right
        
        # إذا كان العنصر الأصغر ليس العنصر الحالي، نبدلهما ونستمر في النقل للأسفل
        if min_idx != i:
            self.heap[i], self.heap[min_idx] = self.heap[min_idx], self.heap[i]
            self._sift_down(min_idx)
    
    def size(self):
        """إرجاع حجم الكومة."""
        return len(self.heap)

# مثال للاستخدام
min_heap = MinHeap()

# إدراج عناصر
min_heap.insert(10)
min_heap.insert(5)
min_heap.insert(20)
min_heap.insert(1)
min_heap.insert(30)

# استخراج العناصر بترتيب تصاعدي
print("العناصر بترتيب تصاعدي:")
while min_heap.size() > 0:
    print(min_heap.extract_min())

تنفيذ الخوارزمية بلغة C++:

#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;

typedef pair<int, int> pii; // زوج (المسافة، الرأس)

class Graph {
private:
    int V;  // عدد الرؤوس
    vector<vector<pii>> adj;  // قائمة المجاورة: (الرأس المجاور، الوزن)
    
public:
    // المنشئ
    Graph(int vertices) {
        V = vertices;
        adj.resize(V);
    }
    
    // إضافة حافة في الرسم البياني
    void addEdge(int u, int v, int weight) {
        adj[u].push_back(make_pair(v, weight));
        adj[v].push_back(make_pair(u, weight));  // يُحذف هذا السطر للرسم البياني الموجه
    }
    
    // خوارزمية ديكسترا
    vector<int> dijkstra(int src) {
        // أولوية معكوسة: لاختيار العنصر ذو المسافة الأقل
        priority_queue<pii, vector<pii>, greater<pii>> pq;
        
        // مصفوفة المسافات
        vector<int> dist(V, INT_MAX);
        
        // إضافة المصدر إلى طابور الأولوية وتعيين مسافته بـ 0
        pq.push(make_pair(0, src));
        dist[src] = 0;
        
        // طالما لم يتم معالجة جميع الرؤوس
        while (!pq.empty()) {
            // استخراج الرأس ذو المسافة الأقل
            int u = pq.top().second;
            pq.pop();
            
            // تكرار على جميع الرؤوس المجاورة لـ u
            for (auto& neighbor : adj[u]) {
                int v = neighbor.first;        // الرأس المجاور
                int weight = neighbor.second;  // وزن الحافة
                
                // إذا وُجد مسار أقصر
                if (dist[v] > dist[u] + weight) {
                    // تحديث المسافة
                    dist[v] = dist[u] + weight;
                    pq.push(make_pair(dist[v], v));
                }
            }
        }
        
        return dist;
    }
    
    // طباعة المسافات من المصدر إلى جميع الرؤوس الأخرى
    void printDistances(vector<int> dist, int src) {
        cout << "المسافات من الرأس " << src << " إلى جميع الرؤوس الأخرى:" << endl;
        for (int i = 0; i < V; ++i) {
            cout << "الرأس " << i << ": ";
            if (dist[i] == INT_MAX)
                cout << "غير متصل";
            else
                cout << dist[i];
            cout << endl;
        }
    }
};

int main() {
    // إنشاء رسم بياني به 9 رؤوس
    Graph g(9);
    
    // إضافة الحواف
    g.addEdge(0, 1, 4);
    g.addEdge(0, 7, 8);
    g.addEdge(1, 2, 8);
    g.addEdge(1, 7, 11);
    g.addEdge(2, 3, 7);
    g.addEdge(2, 8, 2);
    g.addEdge(2, 5, 4);
    g.addEdge(3, 4, 9);
    g.addEdge(3, 5, 14);
    g.addEdge(4, 5, 10);
    g.addEdge(5, 6, 2);
    g.addEdge(6, 7, 1);
    g.addEdge(6, 8, 6);
    g.addEdge(7, 8, 7);
    
    // تنفيذ خوارزمية ديكسترا من الرأس 0
    vector<int> dist = g.dijkstra(0);
    
    // طباعة المسافات
    g.printDistances(dist, 0);
    
    return 0;
}

تنفيذ خوارزمية كروسكال بلغة Java:

import java.util.*;

class Edge implements Comparable<Edge> {
    int src, dest, weight;
    
    public Edge(int src, int dest, int weight) {
        this.src = src;
        this.dest = dest;
        this.weight = weight;
    }
    
    @Override
    public int compareTo(Edge other) {
        return this.weight - other.weight;
    }
}

class DisjointSet {
    int[] parent, rank;
    
    public DisjointSet(int n) {
        parent = new int[n];
        rank = new int[n];
        
        // في البداية، كل عنصر هو مجموعة بحد ذاتها
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            rank[i] = 0;
        }
    }
    
    // إيجاد جذر المجموعة التي ينتمي إليها x (مع ضغط المسار)
    public int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }
    
    // دمج المجموعتين اللتين ينتمي إليهما x و y
    public void union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        
        if (rootX == rootY) return;
        
        // ربط الشجرة ذات الرتبة الأصغر بالشجرة ذات الرتبة الأكبر
        if (rank[rootX] < rank[rootY]) {
            parent[rootX] = rootY;
        } else if (rank[rootX] > rank[rootY]) {
            parent[rootY] = rootX;
        } else {
            parent[rootY] = rootX;
            rank[rootX]++;
        }
    }
}

public class KruskalMST {
    private int V; // عدد الرؤوس
    private List edges; // قائمة الحواف
    
    public KruskalMST(int v) {
        V = v;
        edges = new ArrayList<>();
    }
    
    // إضافة حافة للرسم البياني
    public void addEdge(int src, int dest, int weight) {
        edges.add(new Edge(src, dest, weight));
    }
    
    // إيجاد شجرة التمدد الصغرى باستخدام خوارزمية كروسكال
    public List kruskalMST() {
        List result = new ArrayList<>();
        
        // ترتيب الحواف تصاعديًا حسب الوزن
        Collections.sort(edges);
        
        // إنشاء مجموعة منفصلة لكل رأس
        DisjointSet ds = new DisjointSet(V);
        
        int edgeCount = 0;
        int i = 0;
        
        // متابعة حتى يتم إضافة V-1 حافة إلى شجرة التمدد
        while (edgeCount < V - 1 && i < edges.size()) {
            // اختيار الحافة التالية ذات الوزن الأقل
            Edge nextEdge = edges.get(i++);
            
            int x = ds.find(nextEdge.src);
            int y = ds.find(nextEdge.dest);
            
            // إذا لم تشكل الحافة دورة، أضفها إلى النتيجة
            if (x != y) {
                result.add(nextEdge);
                ds.union(x, y);
                edgeCount++;
            }
        }
        
        return result;
    }
    
    public static void main(String[] args) {
        int V = 9;
        KruskalMST graph = new KruskalMST(V);
        
        // إضافة الحواف
        graph.addEdge(0, 1, 4);
        graph.addEdge(0, 7, 8);
        graph.addEdge(1, 2, 8);
        graph.addEdge(1, 7, 11);
        graph.addEdge(2, 3, 7);
        graph.addEdge(2, 8, 2);
        graph.addEdge(2, 5, 4);
        graph.addEdge(3, 4, 9);
        graph.addEdge(3, 5, 14);
        graph.addEdge(4, 5, 10);
        graph.addEdge(5, 6, 2);
        graph.addEdge(6, 7, 1);
        graph.addEdge(6, 8, 6);
        graph.addEdge(7, 8, 7);
        
        // إيجاد وطباعة شجرة التمدد الصغرى
        List mst = graph.kruskalMST();
        
        System.out.println("حواف شجرة التمدد الصغرى:");
        int totalWeight = 0;
        for (Edge edge : mst) {
            System.out.println(edge.src + " -- " + edge.dest + " == " + edge.weight);
            totalWeight += edge.weight;
        }
        System.out.println("الوزن الكلي لشجرة التمدد الصغرى: " + totalWeight);
    }
}

تنفيذ الترتيب الطوبولوجي باستخدام DFS بلغة Python:

from collections import defaultdict

class Graph:
    def __init__(self, vertices):
        self.graph = defaultdict(list)
        self.V = vertices
    
    def add_edge(self, u, v):
        """إضافة حافة من u إلى v"""
        self.graph[u].append(v)
    
    def topological_sort_util(self, v, visited, stack):
        """دالة مساعدة لدالة الترتيب الطوبولوجي"""
        # تأشير الرأس الحالي كمزار
        visited[v] = True
        
        # تكرار لجميع الرؤوس المجاورة للرأس الحالي
        for neighbor in self.graph[v]:
            if not visited[neighbor]:
                self.topological_sort_util(neighbor, visited, stack)
        
        # إضافة الرأس الحالي إلى المكدس الذي يخزن الترتيب
        stack.append(v)
    
    def topological_sort(self):
        """الدالة الرئيسية للترتيب الطوبولوجي"""
        # تأشير جميع الرؤوس كغير مزارة
        visited = [False] * self.V
        stack = []
        
        # استدعاء الدالة المساعدة على جميع الرؤوس غير المزارة
        for i in range(self.V):
            if not visited[i]:
                self.topological_sort_util(i, visited, stack)
        
        # إرجاع الترتيب الطوبولوجي (معكوس لأننا نستخدم مكدس)
        return stack[::-1]

# مثال للاستخدام
g = Graph(6)
g.add_edge(5, 2)
g.add_edge(5, 0)
g.add_edge(4, 0)
g.add_edge(4, 1)
g.add_edge(2, 3)
g.add_edge(3, 1)

print("الترتيب الطوبولوجي للرسم البياني:")
print(g.topological_sort())

تنفيذ الخوارزمية بلغة Java:

import java.util.ArrayList;
import java.util.List;

public class KMPAlgorithm {
    // إعداد مصفوفة البادئات-اللواحق
    private static int[] computeLPSArray(String pattern) {
        int m = pattern.length();
        int[] lps = new int[m];
        
        int len = 0;  // طول أطول بادئة-لاحقة السابقة
        int i = 1;    // مؤشر للنمط
        
        // lps[0] دائماً 0
        lps[0] = 0;
        
        // حساب lps[i] للـ i من 1 إلى m-1
        while (i < m) {
            if (pattern.charAt(i) == pattern.charAt(len)) {
                len++;
                lps[i] = len;
                i++;
            } else {
                if (len != 0) {
                    // استخدم القيم المحسوبة مسبقاً لتجنب العودة للخلف
                    len = lps[len - 1];
                } else {
                    // لا يوجد بادئة-لاحقة مشتركة
                    lps[i] = 0;
                    i++;
                }
            }
        }
        
        return lps;
    }
    
    // خوارزمية KMP للبحث عن النمط في النص
    public static List kmpSearch(String text, String pattern) {
        List result = new ArrayList<>();
        int n = text.length();
        int m = pattern.length();
        
        // حالة خاصة: نمط فارغ
        if (m == 0) {
            return result;
        }
        
        // حساب مصفوفة LPS
        int[] lps = computeLPSArray(pattern);
        
        int i = 0;  // مؤشر للنص
        int j = 0;  // مؤشر للنمط
        
        while (i < n) {
            // تطابق الأحرف
            if (pattern.charAt(j) == text.charAt(i)) {
                i++;
                j++;
            }
            
            // وجدنا تطابقاً كاملاً
            if (j == m) {
                result.add(i - j);  // إضافة موقع بداية التطابق
                j = lps[j - 1];     // البحث عن التطابق التالي
            }
            // عدم تطابق بعد مطابقة j حرف
            else if (i < n && pattern.charAt(j) != text.charAt(i)) {
                if (j != 0) {
                    j = lps[j - 1];
                } else {
                    i++;
                }
            }
        }
        
        return result;
    }
    
    public static void main(String[] args) {
        String text = "ABABDABACDABABCABAB";
        String pattern = "ABABCABAB";
        
        List positions = kmpSearch(text, pattern);
        
        if (positions.isEmpty()) {
            System.out.println("النمط غير موجود في النص");
        } else {
            System.out.println("النمط موجود في المواقع التالية:");
            for (int pos : positions) {
                System.out.println(pos);
            }
        }
    }
}

التعقيد الزمني: O(n+m) - أفضل بكثير من خوارزمية البحث القوية.