rr算法代码

以下是一个简单的Rabin-Karp字符串匹配算法的实现：

def rabin_karp(pattern, text):
    pattern_hash = hash(pattern)
    for i in range(len(text) - len(pattern) + 1):
        if hash(text[i:i+len(pattern)]) == pattern_hash:
            if text[i:i+len(pattern)] == pattern:
                return i
    return -1

这个算法的时间复杂度是O(nm)，其中n是文本长度，m是模式长度。因为它使用了哈希函数来计算子串的哈希值，所以它能够在平均O(1)的时间内比较两个子串，从而提高匹配的速度。

相关问题

c++模拟实现RR算法和SJF算法代码实验

以下是C++语言实现RR算法和SJF算法的代码：

RR算法实现：

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

struct Process {
    int pid; // 进程ID
    int burst_time; // 执行时间
    int remain_time; // 剩余时间
    int arrival_time; // 到达时间
    int waiting_time; // 等待时间
    int turnaround_time; // 周转时间
};

void RR(vector<Process> processes, int quantum) {
    queue<Process> ready_queue;
    int total_time = 0;
    int n = processes.size();
    int completed = 0;
    int current_time = 0;
    for (int i = 0; i < n; i++) {
        total_time += processes[i].burst_time;
        processes[i].remain_time = processes[i].burst_time;
    }
    while (completed < n) {
        for (int i = 0; i < n; i++) {
            if (processes[i].arrival_time <= current_time && processes[i].remain_time > 0) {
                ready_queue.push(processes[i]);
            }
        }
        if (ready_queue.empty()) {
            current_time++;
            continue;
        }
        Process current_process = ready_queue.front();
        ready_queue.pop();
        int execution_time = min(quantum, current_process.remain_time);
        current_time += execution_time;
        current_process.remain_time -= execution_time;
        if (current_process.remain_time <= 0) {
            completed++;
            current_process.turnaround_time = current_time - current_process.arrival_time;
            current_process.waiting_time = current_process.turnaround_time - current_process.burst_time;
            cout << "Process " << current_process.pid << " completed." << endl;
            cout << "Turnaround time: " << current_process.turnaround_time << endl;
            cout << "Waiting time: " << current_process.waiting_time << endl;
        } else {
            ready_queue.push(current_process);
        }
    }
}

int main() {
    vector<Process> processes = {
        {1, 10, 0, 0, 0},
        {2, 5, 0, 1, 0},
        {3, 8, 0, 2, 0},
        {4, 3, 0, 3, 0},
        {5, 7, 0, 4, 0}
    };
    int quantum = 2;
    RR(processes, quantum);
    return 0;
}

SJF算法实现：

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

struct Process {
    int pid; // 进程ID
    int burst_time; // 执行时间
    int arrival_time; // 到达时间
    int waiting_time; // 等待时间
    int turnaround_time; // 周转时间
};

bool compare(const Process& a, const Process& b) {
    return a.burst_time < b.burst_time;
}

void SJF(vector<Process> processes) {
    sort(processes.begin(), processes.end(), compare);
    int n = processes.size();
    int current_time = 0;
    for (int i = 0; i < n; i++) {
        current_time += processes[i].burst_time;
        processes[i].turnaround_time = current_time - processes[i].arrival_time;
        processes[i].waiting_time = processes[i].turnaround_time - processes[i].burst_time;
        cout << "Process " << processes[i].pid << " completed." << endl;
        cout << "Turnaround time: " << processes[i].turnaround_time << endl;
        cout << "Waiting time: " << processes[i].waiting_time << endl;
    }
}

int main() {
    vector<Process> processes = {
        {1, 10, 0, 0, 0},
        {2, 5, 1, 0, 0},
        {3, 8, 2, 0, 0},
        {4, 3, 3, 0, 0},
        {5, 7, 4, 0, 0}
    };
    SJF(processes);
    return 0;
}

RR算法python代码

以下是RR算法的Python代码：

def round_robin(processes, quantum):
    n = len(processes)
    waiting_time = [] * n
    turnaround_time = [] * n
    remaining_time = [p[1] for p in processes]
    current_time = 
    while True:
        done = True
        for i in range(n):
            if remaining_time[i] > :
                done = False
                if remaining_time[i] > quantum:
                    current_time += quantum
                    remaining_time[i] -= quantum
                else:
                    current_time += remaining_time[i]
                    turnaround_time[i] = current_time - processes[i][]
                    waiting_time[i] = turnaround_time[i] - processes[i][1]
                    remaining_time[i] = 
        if done:
            break
    return waiting_time, turnaround_time

希望对你有帮助！