editDistanceOpenmp.cpp

#include <stdio.h>
#include <string>
#include <set>
#include<iostream>
#include <time.h>
#include <omp.h>
using namespace std;


class EditDistance {
    
    private:

    	string firstString;
        string secondString;
    	int firstStringLength;
    	int secondStringLength;
	    int editMatrix[1500][1500];
    	int i, j;
    	
    public:

    	EditDistance(string firstStringP, string secondStringP) {
		firstString = firstStringP;
		secondString = secondStringP;
		firstStringLength = firstString.size();
		secondStringLength = secondString.size();
	}
	
	int min3(int a, int b, int c) {
		return (a < b ? std::min(a, c) : std::min(b, c));
	}

	int calculate(int fi, int ff, int si, int sf ) {

		int i, j;
		for (i = fi; i < ff + 1; i++) {
			for (j = si; j < sf + 1; j++) {
				if (i == 0 || j == 0) {
				    editMatrix[i][j] = std::max(i, j);
				} else {
					editMatrix[i][j] = min3(
							editMatrix[i - 1][j] + 1,
							editMatrix[i][j - 1] + 1,
							editMatrix[i - 1][j - 1] + (firstString.at(i - 1) != secondString.at(j - 1) ? 1 : 0));
				}
			}
		}

		cout << " ";
		cout << "La distanza ? " << editMatrix[firstStringLength][secondStringLength];
	    return 0;
	}

};

int main()
{
    EditDistance ed("gagcccgtttcggatattcgcctttcggccaaaaatatggaatttagatagtccttgtgtgcggcctgtcatggttagagccacttagctataggatacccctgccttgcattgcgcggctcctggtgggttcgtaagacgtccaaagagatgc", "gagcccgtttcggatattcgcctttcggccaaaaatatggaatttagatagtccttgtgtgcggcctgtcatggttagagccacttagctataggatacccctgccttgcattgcgcggctcctggtgggttcgtaagacgtccaaagagatgc");
    clock_t tStart = clock();
    ed.calculate(0, 750, 0, 750);
    #pragma omp parallel sections
    {
        #pragma omp section
        ed.calculate(751, 1500, 0, 750);
        #pragma omp section
        ed.calculate(0, 750, 751, 1500);
    }
    ed.calculate(751, 1500, 751, 1500);
    cout << "\n";
    printf("Time taken: %.5fs\n", (double)(clock() - tStart)/CLOCKS_PER_SEC);
    return 0;
}