OpenMP C++ program with Vectors

Question

I wrote a OpenMP program in C++ which basically finds the suffix-prefix overlap of a given length. All my strings are stored in a vector and I have two for loops for checking the overlap (all against all). I am trying to make the for loop parallel, but it does not improve the time. Following is my program

    vector<string> Reads; // contains all strings 
    vector<int> *AdjList = new vector<int>[Reads.size()];
    vector<int> *OLL = new vector<int>[Reads.size()];

     // int i,j;
    /*# pragma omp parallel \
      shared ( AdjList, OLL ) \
      private ( i, j )*/
    #pragma omp parallel for
    for(int i=0; i<Reads.size(); i++){
      string suff = Reads.at(i).substr(Reads.at(i).length() - minOLL, minOLL);
      for(int j=0; j<Reads.size(); j++){
        if(i != j){
          size_t found = rabin_karp(suff, Reads.at(j));
          if(found != -1){
            string pref1 = Reads.at(j).substr(0, found);
            string suff1 = Reads.at(i).substr(Reads.at(i).length() - minOLL - found, found);
            if(pref1.compare(suff1) == 0){
              AdjList[i].push_back(j);
              OLL[i].push_back(found + minOLL);
            }
          }
        }
      }
    }

I guess reduction might help, but I am clueless about how to use it

Answer 1

1.since size of strings may be different you may use schedule(dynamic) so the tasks dynamically assigned to threads. 2. you can split inner loop into two loops to get rid of if statement. 3. substr is not a good choice because leads to creation of new string so you may use and save character positions to speed the code. However below applied 1, 2 mentioned cases:

#pragma omp parallel for schedule(dynamic)
for(int i=0; i<Reads.size(); i++){
  string suff = Reads.at(i).substr(Reads.at(i).length() - minOLL, minOLL);
  for(int j=0; j< i; j++){
      size_t found = rabin_karp(suff, Reads.at(j));
      if(found != -1){
        string pref1 = Reads.at(j).substr(0, found);
        string suff1 = Reads.at(i).substr(Reads.at(i).length() - minOLL - found, found);
        if(pref1.compare(suff1) == 0){
          AdjList[i].push_back(j);
          OLL[i].push_back(found + minOLL);
        }
      }
  }
  for(int j=i+1; j< Reads.size(); j++){
      size_t found = rabin_karp(suff, Reads.at(j));
      if(found != -1){
        string pref1 = Reads.at(j).substr(0, found);
        string suff1 = Reads.at(i).substr(Reads.at(i).length() - minOLL - found, found);
        if(pref1.compare(suff1) == 0){
          AdjList[i].push_back(j);
          OLL[i].push_back(found + minOLL);
        }
      }
  }
}