Finding the most common phrase in a list of sentences

Question

I need to write code in C to find most common phrases in a file of sentences.

• Each sentence has only lower case English words and ends with a linebreak/endline.
• A phrase is defined as 3 consecutive words so there can be "(total no of words -2)" phrases in each sentence.
• A phrase is common if it occurs in each sentence.

Here's my implementation but I am not getting desired results, please help and give me some new ideas as well. Thank you.

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<unistd.h>

#define N 1000

int fetchLine();
char line [N][100];
int hash(int max,int line_max);
void divide(char sent[100],char phrase[100][60],int hash[100],int i,int max);

int main()
{
  int lin,i;
  char sent1[100];
  lin = fetchLine();
  //printf("%d \n",lin);

  /*
    for (i=0;i<lin;i++)
    {
    printf("%s",line[i]);
    printf("\n");
    }
  */

  int word=0;
  strcpy(sent1,line[0]);
  //puts(sent1);

  /*
    for (i=0; sent1[i]!='\0';i++)
    {
    if (sent1[i]==' ')
    word++;
    }
    word = word+1;
  */

  // finding no of words
  char *args ,arg[20][20];
  args=strtok(sent1," ");

  for(i=0;args!=NULL;i++)
    {
      strcpy(arg[i],args);
      args = strtok(NULL," ");
    }

  word=i;
  //printf("%d \n",word);
  int phrase_count=word-2;
  int k=hash(phrase_count,lin);

  if (k==0)
    printf("\nNo common phrase exists\n ");

  return 0;
}


int fetchLine()
{
  FILE *f1;
  f1=fopen("file.txt","r");
  char c;
  int i=0,j=0;
  while ( (c=getc(f1)) !=EOF)
    {
      if (c=='\n')
        {
          i++;
          j=0;
        }
      line[i][j++]=c;
    }
  return i;
}

int hash(int max,int line_max)
{
  //printf("%d",line_max);
  //printf("%d",max);
  int hash_table[max];
  // for line 0
  char phrase[max][60],sent[100];
  strcpy(sent,line[0]);
  char *args ,arg[20][20];
  args=strtok(sent," ");

  int i,j,t;

  for(i=0;args!=NULL;i++)
    {
      strcpy(arg[i],args);
      args = strtok(NULL," ");
    }

  for (i=0;i<max;i++)
    {
      strcpy(phrase[i],arg[i]);
      strcat(phrase[i],arg[i+1]);
      strcat(phrase[i],arg[i+2]);
      //puts(phrase[i]);
    }

  for(i=0;i<max;i++) // hashtable initialised
    hash_table[i]=1;
  int word;

  for (i=1; i<line_max;i++)
    {
      strcpy(sent,line[i]);
      //puts(sent);
      divide(sent,phrase,hash_table,i,max);
    }

  //for (i=0; i< max;i++)
  // printf("%d \n",hash_table[i]);

  int count=0;
  for (i=0;i<max;i++)
    {
      if (hash_table[i]== (line_max))
        {   count++;
          printf("The following phrase is frequent");
          puts(phrase[i]);
        }
    }

  if (count == 0 )
    return 0;
  else
    return 1;
}

void divide(char sent[100],char phrase[100][60],int hash[100],int i,int max)
{
  int word,j,t,n;
  // puts(sent);
  printf("%d",i);
  char temp[100][60];
  char *args ,arg[20][20];
  args=strtok(sent," ");

  for (j=0;j<max;j++)
    puts(phrase[j]);

  for(word=0;args!=NULL;word++)
    {
      strcpy(arg[word],args);
      args = strtok(NULL," ");
    }
  //printf("%d",word);
  word= (word-2);

  for (t=0;t<word;t++)
    {
      strcpy(temp[t],arg[t]);
      strcat(temp[t],arg[t+1]);
      strcat(temp[t],arg[t+2]);
      puts(temp[t]);
    }

  for (j=0;j<max;j++)
    {
      for (t=0;t<word;t++)
        {
          if (n=(strcmp(phrase[j],temp[t]))==0)
            {
              if (hash[j]==i)
                { hash[j]=hash[j]+1;
                  printf("%d %d",j,hash[j]);}
            }
        }
    }

  for (j=0; j< max;j++)
    printf("%d \n",hash[j]);

  free(args);
}

Answer 1

A few comments on the code...

• turn ON more compiler warnings
• remove commented-out code when submitting code
• reverse the order of functions so that no prototypes are needed.
• if a function has no parameters, declare it with a void parameter list, eg. int func(void)
• main has parameters: int main(int argc, char ** argv);
• many of your for-loops should be extracted into functions. It is sometimes necessary to have several loops in the same function, but much more common to have only one.
• nested loops are generally bad practice in my opinion. Often the inner loop can be extracted to a separate function.
• only use free on memory that you know has been dynamically allocated (incorrect: free(args) in divide())
• strcpy and strcat can overflow the target buffer and are therefore frequently used unsafely.
• don't use embedded constants (100, 60 etc)
• specifying the size of a one-dimensional array in a parameter list has no effect
• for 2-dimensional arrays, only the 2nd size is significant.
• 2-dimensional arrays are confusing (to me). I prefer to define an array type and an array.

For example:

typedef char Line[100];
Line lines [100];

And then functions can be:

static void function(Line * lines) {...}

and the caller can do:

{
    Line mylines [100];
    ...
    function(mylines);

This will generate the same code as explicit 2-D arrays, but to me is easier to read. Perhaps other readers have different opinions on that...?

And note, from above:

Your if statement if (n=(strcmp(phrase[j],temp[t]))==0) has a misplaced bracket. The compiler will have told you that if you have enough warnings enabled. It should read if ((n=strcmp(phrase[j],temp[t]))==0)