Something similar to LCS

[tomtran3110]

Well this is my assignment: https://github.com/SytemProgramming2015FallatNTU/Announcement/wiki/Homework-1
Don't worry about the due date. I'm working on drawing the table. At my current step, I want to print out the Longest Common Subsequence(the number of the same line). Here is my code:

#include<iostream>
#include<fstream>
#include<string>

using namespace std;

#define MAX 10000000
#define U 1
#define L 2
#define UL 3

void fill_the_table(ifstream& file1, ifstream& file2, int **table, int **p){
  table[0][0]=0;
  p[0][0]=UL;
  string line1, line2;
  int i, j;
  while(getline(file1, line1)){
    table[0][j]=0;
    p[0][j]=L;
    while(getline(file2, line2)){
      table[i][0]=0;
      p[i][0]=L;
      if(line1==line2){
        table[i][j]=p[i-1][j-1]+1;
        p[i][j]=UL;
        i++;
      }
      else{
        if(table[i-1][j]>table[i][j-1]){
          table[i][j]=table[i-1][j];
          p[i][j]=U;
        }
        else if(table[i-1][j]<table[i][j-1]){
          table[i][j]=table[i][j-1];
          p[i][j]=L;
        }
        i++;
      }
      j++;
    }
  }
  cout<<table[i][j];
}

void table(ifstream& file1, ifstream& file2){
  int i=0, j=0;
  string line1, line2;

  while(getline(file1, line1)){
    i++;
  }
  while(getline(file2, line2)){
    j++;
  }
  int** table = new int* [i];
  for(int a=0; a<i; a++){
    table[a] = new int [j];
  }

  int** p = new int* [i];
  for(int a=0; a<i; a++){
    p[a] = new int [j];
  }

  fill_the_table(file1, file2, table, p);

  for(int a=0; a<i; a++){
    delete[] table[j];
  }
  delete table;

  for(int a=0; a<i; a++){
    delete[] p[j];
  }
  delete p;

  return;
}

int main(int argc, char* argv[]){
  ifstream file1(argv[1]);
  ifstream file2(argv[2]);
  table(file1, file2);
}

[tomtran3110]

Now I got another problem. I tried to getline() from the start again using file1.clear() and file2.clear(), but it seems that it has some problem with passing the file or the table or p?

[coder777]

clear() is only for clearing the error state. You need the seek.() function in order to move the read/write pointer:

http://www.cplusplus.com/reference/istream/istream/seekg/?kw=seekg

I'd suggest that you read the lines into two vector<string> for each file.

What are you trying to do with this int **table / int **p?

[tomtran3110]

Both of them is made for drawing the LCS table. "table" stores the numbers, and "p" stores where the numbers coming from...

It is something like this:
http://staff.ustc.edu.cn/~csli/graduate/algorithms/book6/318_a.gif

The numbers and the arrows I supposed.

[tomtran3110]

Thanks for your information now I can read from the start with:

file1.clear();
file1.seekg(0, ios::beg);

But it seems that the program stop at the "fill_the_table()" function, precisely the inner while loop after it run one time.

[coder777]

Yes it does. Line 16: int i, j; remain uninitialized. Set them to 0.

You might use a for loop, e.g.: for(int i = 0; getline(file1, line1); ++i){

So what's wrong with vector?

http://www.cplusplus.com/reference/vector/vector/?kw=vector

[tomtran3110]

I initialize it int i=1, j=1;. It still the same...

And nothing wrong with vector... It is "a stranger" to me...

[coder777]

I initialize it int i=1, j=1;. It still the same...

This will go out of bounds at the end of the loop.

if you start with i=0 this p[i-1][j-1] will crash. Instead of start with 1 check if i/j isn't 0.

And nothing wrong with vector... It is "a stranger" to me...

It is by far easier to deal with vector. Since this is rather complex you should be able to use vector.

If you want to find Longest Common Subsequence with vector you'd do this:

- Find a sentence from vector1 in vector2 (there's already a find function).
- Count the subsequent equal sentence from vector1 in vector2.
- Repeat for all sentence in vector1.

Oh and: For some reason I can't open the gif link.