Substring searching with Knuth–Morris–Pratt

My program uses the Knuth–Morris–Pratt algorithm to search for a particular substring in a .txt file and then store it in a binary search tree.

Note that testfile.txt should be contain only spaces and normal characters (no newlines! - except maybe as the last byte).

There is a lot of code, so note that I am primarily concerned about the KMP algorithm in countWord.c, which I am new to.

wordCount.h

#ifndef WORDCOUNT_H
#define WORDCOUNT_H
#include<stdlib.h>
#include<stdio.h>

typedef struct BSTnode{
char data[20];
struct BSTnode* leftchild;    //if less than, put it on the left
struct BSTnode* rightchild;   //if greater than, on the right
int num;

}BSTnode;

char* findWord(FILE*);       //This function is used to find out a new word again and again in the file.
int countWord(FILE*,char*);  //this is used to count out occurrences of the word found
int inputWord(BSTnode*,char*,int);    //this is used to insert the word into the binary search tree(but I don' try to loop through the tree)
int createTable(char*,int,int*);   //this function is for the KMP algorithm

#endif


main.c

#include<stdlib.h>
#include<stdio.h>
#include<string.h>
#include<stdbool.h>
#include "wordCount.h"

char arr[20]={0};

int main()
{
/*initialize the firstNode*/
BSTnode* firstNode=malloc(sizeof(BSTnode));
firstNode->leftchild=NULL;
firstNode->rightchild=NULL;
strcpy(firstNode->data,"");
firstNode->num=0;

FILE* fs=fopen("testfile.txt","r");
if(!fs){
printf("Failed to open fiel!!\n");
return 2;
}

int i=0;
while(++i<=30){         //To keep it simple, I only find out 30 words and search it in the testfile.txt
memset(arr,'\0',20);
char* newWord=findWord(fs);

int totalNumberOfTheWord=countWord(fs,newWord);

inputWord(firstNode,newWord,totalNumberOfTheWord);
}

return 0;

}


findWord.c

#include<string.h>
#include<stdio.h>
#include<stdbool.h>
#include<stdlib.h>
#include "wordCount.h"

extern char arr[20];
char* findWord(FILE* fs)
{

static long pos=0;
fseek(fs,pos,SEEK_SET);

if(ferror(fs)){
perror("fseek() failed!!!\n");
fprintf(stderr,"fseek() failed in file %s\n",__FILE__);
exit(EXIT_FAILURE);
}
char chr[1]={'\0'};
bool flag1=false;
bool flag2=false;
/* I set two bool vars(flag1 and flag2) to make findWord() find only one
* word(with only normal characters, no space, no newline*/

if(chr[0]!=32){
strncat(arr,chr,1);
flag2=true;
flag1=true;
}
else
flag1=false;
}

pos=ftell(fs)-1;
//maybe everytime you use "fseek()", "ftell()", the
//file-position will move one byte ahead.
return arr;
}


countWord.c

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <stdbool.h>
#include "wordCount.h"

int next[20]={0};

/*create table of the word for search. this table is for using KMP algorithm*/
int createTable(char* word, int lengthOfWord, int* next){
int i=0;
int j=-1;
next[0]=-1;

while(i<lengthOfWord-1){
if(j==-1||word[i]==word[j]){
++i;
++j;
next[i]=j;
}

else{
j=next[j];
}
}

return 0;
}

int countWord(FILE* fs,char* word)
{
rewind(fs);
fseek(fs,0L,SEEK_END);
int lengthOfBuf=ftell(fs);
char* buf=calloc(1,sizeof(char)*lengthOfBuf+1);
if(!buf){
perror("Memory allocation failed!!\n");
exit(1);
}

rewind(fs);
/*read the content of testfile.txt into buf*/
perror("File not read into buf yet!");
exit(1);
}

int lengthOfWord=strlen(word);
createTable(word,lengthOfWord,next);

int posOfBuf=0;
int posOfWord=-1;
int count=0;

while(posOfBuf<lengthOfBuf-1){
if(posOfWord==-1||(word[posOfWord]==buf[posOfBuf])||(word[posOfWord]-buf[posOfBuf]==32)||(word[posOfWord]-buf[posOfBuf]==-32)){
if(posOfWord==lengthOfWord-1){
count+=1;
posOfWord=-1;
continue;
}
else{
++posOfWord;
++posOfBuf;
}

}

else
posOfWord=next[posOfWord];
}

return count;
}


inputWord.c

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include"wordCount.h"

/*input a the word and its occurrences into the binary search tree(but not trying to print the tree out*/

int inputWord(BSTnode* Node,char* word,int num){

BSTnode* ptr=Node;
while(1){
if(stricmp(word,ptr->data)>0){
if(ptr->rightchild!=NULL){
ptr=ptr->rightchild;
continue;
}
else{
ptr->rightchild=malloc(sizeof(BSTnode));
if(!(ptr->rightchild)){
perror("Failed to allocate memory for right-child!");
exit(1);
}
ptr=ptr->rightchild;
ptr->rightchild=NULL;
ptr->leftchild=NULL;
strcpy(ptr->data,word);
ptr->num=num;
fprintf(stdout,"New data '%s(%d)' successfully inserted into a new (left) node at (value of pointer)\n",word,num);
break;
}
}

else if(stricmp(word,ptr->data)<0){
if(ptr->leftchild!=NULL){
ptr=ptr->leftchild;
continue;
}
else{
ptr->leftchild=malloc(sizeof(BSTnode));
if(!(ptr->leftchild)){
perror("Failed to allocate memory for left-child!");
exit(1);
}
ptr=ptr->leftchild;
ptr->leftchild=NULL;
ptr->rightchild=NULL;
strcpy(ptr->data,word);
ptr->num=num;
fprintf(stdout,"New data '%s(%d)' successfully inserted into a new (left) node at (value of pointer)\n",word,num);
break;
}
}
else{
fprintf(stdout,"It is the same word!!\n");
return 0;
}
}

return 0;
}

• Now you know the danger of dropping braces! – Veedrac Jun 23 '15 at 13:46
• I miss that when I paste my code and modified it... – Alex Jun 23 '15 at 13:51
• Why did you modify it after pasting it? Is the above code your real code that you know works? – rolfl Jun 23 '15 at 13:54
• @rolfl yes it is. I modify it because there are so many trivial printf() statement (for test) in my original code. – Alex Jun 23 '15 at 14:13
• @rolfl the code in my post can be compiled and run – Alex Jun 23 '15 at 14:14

I'll only focus on countWord.c.

Indentation/Spacing

I'm not sure what happened to your indentation in countWord() but it is all over the place. It was hard for me to figure out which code belonged in which blocks.

Your code could use some more spaces. It's hard to read code like this:

    if(j==-1||word[i]==word[j]){


Better would be this:

    if (j == -1 || word[i] == word[j]) {


Incorrect if

This line of code is incorrect:

   if(!lengthOfBuf==fread(buf,1,lengthOfBuf,fs)){


Assuming a nonempty file, the line above translates to:

   if(0==fread(buf,1,lengthOfBuf,fs)){


You probably meant this:

   if (lengthOfBuf != fread(buf,1,lengthOfBuf,fs)) {


Unnecessary global

The next array is global, but it could easily be moved to be a local variable of the countWord() function.

Upper/lowercase comparison

You currently have a triple check to see if one letter is -32, 0, or +32 away from the other letter. You can do better with:

if (((c1 ^ c2) & ~32) == 0)


where c1 and c2 are two characters you are trying to compare.

Use const keyword

You should use const on arguments that are not written to. In your case, the word argument for both createTable() and countWord() could be marked const.