Notes

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

#define key ""

int mainLength;

typedef struct Branch Branch;
struct Branch
{
char *value;
Branch *subBranches; // Branch array with size of mainLength
Branch *parentBranch;
};

char *takeString()
{
FILE *file = fopen("/home/emre/Masaüstü/data.txt", "r");

int c;
int length = 2;
char *buf = malloc(sizeof(char) * length);
if (buf == NULL)
{
printf("nnERROR NO: 06nn");
exit(1);
}

while ((c = fgetc(file)) != EOF && c != 'n')
{
buf = realloc(buf, sizeof(char) * length);
if (buf == NULL)
{
printf("nnERROR NO: 05nn");
exit(1);
}

buf[length - 2] = c;

length += 1;
}

buf[length - 2] = '';

return buf;
}

char *strrev(char *str)
{
char *p1, *p2;

if (!str || !*str)
return str;
for (p1 = str, p2 = str + strlen(str) - 1; p2 > p1; ++p1, --p2)
{
*p1 ^= *p2;
*p2 ^= *p1;
*p1 ^= *p2;
}
return str;
}

// Using for comparing two strings. Returns value of same prefix length.
int compareForIndexes(char *wordOne, char *wordTwo)
{
int lengthOne = strlen(wordOne);
int lengthTwo = strlen(wordTwo);

int minLength;

if (lengthOne < lengthTwo)
{
minLength = lengthOne;
}
else
{
minLength = lengthTwo;
}

for (int i = 0; i < minLength; i++)
{
if (wordOne[i] != wordTwo[i])
{
return i;
}
}
return minLength;
}

// Create branch with empty subBranches. Connects to the parent.
Branch createBranch(char *value, int subBranchNumber, Branch *parenting)
{
// This is for creating empty subbranches.
Branch *subBranches = (Branch *)malloc(subBranchNumber * sizeof(Branch));

// That's gonna return at last of the function.
Branch *newBranch = (Branch *)malloc(subBranchNumber * sizeof(Branch));

if (newBranch)
{
newBranch[0].parentBranch = NULL;
newBranch[0].subBranches = NULL;
newBranch[0].value = NULL;
}
else
{
printf("nnERROR NO: 03nn");
exit(1);
}

for (int a = 0; a < subBranchNumber; a++)
{
Branch *newSubBranch = (Branch *)malloc(sizeof(Branch *));

newSubBranch[0].value = NULL;
newSubBranch[0].parentBranch = newBranch;
newSubBranch[0].subBranches = NULL;

subBranches[a] = newSubBranch[0];
}

newBranch[0].value = value;
newBranch[0].subBranches = subBranches;
newBranch[0].parentBranch = parenting;

return newBranch[0];
}

// Returns number of subbranches.
int getBranchNumber(Branch branch)
{
if (branch.subBranches == NULL)
return 0;

for (int a = 0;; a++)
{
if (branch.subBranches[a].value == NULL)
{
return a;
}
}

printf("nnERROR NO: 01nn");
exit(1);
}

// Just adds subbranch to another branch. Don't use directly.
void simplyAddBranch(Branch mainBranch, Branch subBranch)
{
Branch *sending = (Branch *)malloc(sizeof(Branch));
sending[0] = subBranch;

mainBranch.subBranches[getBranchNumber(mainBranch)] = sending[0];
return;

printf("nnERROR NO: 02nn");
exit(1);
}

// Splits a string to two strings with index.
void splitString(char *mainString, int index, char *wordOne, char *wordTwo)
{
for (int a = 0; a < strlen(mainString); a++)
{
if (a < index)
{
wordOne[a] = mainString[a];
}
else
{
wordTwo[a - index] = mainString[a];
}
}
}

// Adds one suffix to branch but checks every subbranches for suffix tree rules.
void addSuffixToBranch(Branch branch, char *word)
{
if (getBranchNumber(branch) == 0)
{
Branch *newBranch = (Branch *)malloc(sizeof(Branch *));
newBranch[0] = createBranch(word, mainLength, &branch);

simplyAddBranch(branch, newBranch[0]);
return;
}

Branch currentBranch = branch.subBranches[0];
char *currentWord = (char *)malloc(sizeof(char) * mainLength);
strcpy(currentWord, word);
int insideNumber = 0;
int branchIndex = 0;

while (1)
{
int differentIndex = compareForIndexes(currentWord, currentBranch.value);

int currentBranchNumber = getBranchNumber(currentBranch.parentBranch[0]);
if (differentIndex == 0)
{
// Next branch
if (currentBranchNumber > branchIndex + 1)
{
branchIndex += 1;
currentBranch = currentBranch.parentBranch->subBranches[branchIndex];
}
else
{
Branch *newBranch = (Branch *)malloc(sizeof(Branch *));
newBranch[0] = createBranch(currentWord, mainLength, currentBranch.parentBranch);

simplyAddBranch(currentBranch.parentBranch[0], newBranch[0]);

return;
}
}
else if (differentIndex < strlen(currentBranch.value))
{
char *firstWord = (char *)malloc(sizeof(char) * mainLength);
char *secondWord = (char *)malloc(sizeof(char) * mainLength);

char *firstValue = (char *)malloc(sizeof(char) * mainLength);
char *secondValue = (char *)malloc(sizeof(char) * mainLength);

splitString(currentWord, differentIndex, firstWord, secondWord);
splitString(currentBranch.value, differentIndex, firstValue, secondValue);

Branch *firstBranch = (Branch *)malloc(sizeof(Branch *));
Branch *secondBranch = (Branch *)malloc(sizeof(Branch *));

firstBranch[0] = createBranch(firstValue, mainLength, currentBranch.parentBranch);
secondBranch[0] = createBranch(secondValue, mainLength, firstBranch);

for (int e = 0; e < getBranchNumber(currentBranch); e++)
{
secondBranch->subBranches[e] = currentBranch.subBranches[e];
secondBranch->subBranches[e].parentBranch = secondBranch;
}

simplyAddBranch(firstBranch[0], secondBranch[0]);

Branch *newBranch = (Branch *)malloc(sizeof(Branch *));
newBranch[0] = createBranch(secondWord, mainLength, firstBranch);
simplyAddBranch(firstBranch[0], newBranch[0]);

currentBranch.parentBranch->subBranches[branchIndex] = firstBranch[0];

return;
}
else
{
char *firstPart = (char *)malloc(sizeof(char) * mainLength);
char *secondPart = (char *)malloc(sizeof(char) * mainLength);

splitString(currentWord, differentIndex, firstPart, secondPart);

stpcpy(currentWord, secondPart);

currentBranch = currentBranch.subBranches[0];
insideNumber++;
branchIndex = 0;
}
}
}

char *takeRandomColor()
{
int r = rand() % 6;

switch (r)
{
case 0:
return "33[0;31m"; // RED
break;

case 1:
return "33[0;32m"; // GREEN
break;

case 2:
return "33[0;33m"; // YELLOW
break;

case 3:
return "33[0;34m"; // BLUE
break;

case 4:
return "33[0;35m"; // PUPRLE
break;

case 5:
return "33[0;36m"; // CYAN
break;

default:
printf("nnERROR NO: 04nn");
exit(1);
}
}

void setDefaultColor()
{
printf("33[0m");
}

int sizeOfWordArray(char **wordArray)
{
int counter = 0;
while (1)
{
if (wordArray[counter] == NULL)
{
break;
}

counter++;
}
return counter;
}

// Printing for branch. Don't use directly. Use printAll() function.
void printBranch(Branch branch, char **prefixColors, int isLastOne)
{
int *branchNumber = (int *)malloc(sizeof(int));
branchNumber[0] = getBranchNumber(branch);

int *colorNumber = (int *)malloc(sizeof(int));
colorNumber[0] = sizeOfWordArray(prefixColors);

for (int i = 0; i < colorNumber[0] - 1; i++)
{
printf("%s", prefixColors[i]);
printf("| ");
}

if (colorNumber[0] > 0)
{
printf("%s", prefixColors[colorNumber[0] - 1]);
}

if (isLastOne)
{
printf("└─%sn", branch.value);
}
else
{
printf("├─%sn", branch.value);
}

setDefaultColor();

if (branchNumber != 0)
{
char *randomColor = takeRandomColor();

char **newPrefixColors = (char **)malloc(sizeof(char) * mainLength * 10);

for (int e = 0; e < colorNumber[0]; e++)
{
char *newPrefix = (char *)malloc(sizeof(char) * mainLength);
strcpy(newPrefix, prefixColors[e]);
newPrefixColors[e] = newPrefix;
}

newPrefixColors[colorNumber[0]] = randomColor;

int test = sizeOfWordArray(newPrefixColors);

for (int a = 0; a < branchNumber[0]; a++)
{
printBranch(branch.subBranches[a], newPrefixColors, (a == branchNumber[0] - 1));
}
}
}

// Prints all the tree.
void printAll(Branch branch)
{
char **prefixColors = (char **)malloc(sizeof(char) * 10 * mainLength);

char *firstPrefix = (char *)malloc(sizeof(char) * 10);
strcpy(firstPrefix, "33[0;37m");
prefixColors[0] = firstPrefix;

for (int a = 1; a < mainLength; a++)
{
prefixColors[a] = NULL;
}

printf("|n");

for (int a = 0; a < getBranchNumber(branch); a++)
{
printBranch(branch.subBranches[a], prefixColors, (a == getBranchNumber(branch) - 1));
}
}

// Returns an array of suffix string.
char **getSuffixes(char *mainWord)
{
char **wordArray = (char **)malloc((strlen(mainWord) + 1) * strlen(mainWord) * sizeof(char));

for (int i = 0; i < strlen(mainWord); i++)
{
char *newWord = (char *)malloc((strlen(mainWord) + 1) * sizeof(char));

strncpy(newWord, &mainWord[i], strlen(mainWord) - i);
newWord[strlen(mainWord) - i] = '';
wordArray[i] = newWord;
}

return wordArray;
}

// Checks if the word can buildable for suffix tree. Returns 1 or 0.
int canBuildTree(char *word)
{
char **wordArray = getSuffixes(word);

for (int i = 0; i < strlen(word); i++)
{
for (int j = 0; j < i; j++)
{
if (compareForIndexes(wordArray[i], wordArray[j]) == strlen(wordArray[i]))
{
return 0;
}
}
}
return 1;
}

// Dives to all subbranches. Don't use directly. Using in findExtremeBranchNumber
void diveToLastBranches(Branch branch, int *counter)
{
for (int a = 0; a < getBranchNumber(branch); a++)
{
if (getBranchNumber(branch.subBranches[a]) == 0)
{
counter[0] += 1;
}
else
{
diveToLastBranches(branch.subBranches[a], counter);
}
}
}

// Returns number of last branches.
int findExtremeBranchNumber(Branch branch)
{
int *counter = (int *)malloc(sizeof(int));
counter[0] = 0;

diveToLastBranches(branch, counter);

if (counter[0] == 0)
{
return 1;
}

return counter[0];
}

// User functions
void printMostPhrase(Branch branch)
{
int max = 0;
int mostIndex = 0;
for (int a = 0; a < getBranchNumber(branch); a++)
{
int extreme = findExtremeBranchNumber(branch.subBranches[a]);
if (extreme > max)
{
max = extreme;
mostIndex = a;
}
}
printf("En cok gecen kelime obegi: %snTam olarak %d kere geçiyor.", branch.subBranches[mostIndex].value, max);
}

char *takeReversedString(char *word)
{
char *reversedWord = (char *)malloc(sizeof(char) * strlen(word));
strcpy(reversedWord, word);
strrev(reversedWord);
return reversedWord;
}

void addCompleteSuffixToArray(Branch branch, char **wordArray, int *manyArray)
{
char *newWord = (char *)malloc(sizeof(char) * mainLength);
Branch currentBranch = branch;

while (currentBranch.value != key)
{
strcat(newWord, takeReversedString(currentBranch.value));
currentBranch = currentBranch.parentBranch[0];
}

strrev(newWord);

manyArray[sizeOfWordArray(wordArray)] = findExtremeBranchNumber(branch);
wordArray[sizeOfWordArray(wordArray)] = newWord;
}

void diveForLongest(Branch branch, char **wordArray, int *manyArray)
{
for (int a = 0; a < getBranchNumber(branch); a++)
{
if (getBranchNumber(branch.subBranches[a]) > 0)
{
addCompleteSuffixToArray(branch.subBranches[a], wordArray, manyArray);
diveForLongest(branch.subBranches[a], wordArray, manyArray);
}
}
}

void printLongestPhrase(Branch branch)
{
char **wordArray = (char **)malloc(sizeof(char) * mainLength * mainLength * mainLength);
int *manyArray = (int *)malloc(sizeof(int) * mainLength * mainLength);

diveForLongest(branch, wordArray, manyArray);

char longestIndex = 0;

for (int a = 1; a < sizeOfWordArray(wordArray); a++)
{
if (strlen(wordArray[a]) > strlen(wordArray[longestIndex]))
{
longestIndex = a;
}
}

printf("nTekrar eden en uzun altkatar: %snTam %d kere geciyor.", wordArray[longestIndex], manyArray[longestIndex]);
}

int isContainsPhrase(Branch branch, char *word)
{
int *branchNumber = (int *)malloc(sizeof(int));
branchNumber[0] = getBranchNumber(branch);

for (int a = 0; a < branchNumber[0]; a++)
{
int sameIndex = compareForIndexes(word, branch.subBranches[a].value);

if (sameIndex == strlen(word))
{
return 1;
}
else if (sameIndex == strlen(branch.subBranches[a].value))
{
char *wordOne = (char *)malloc(sizeof(char) * mainLength);
char *wordTwo = (char *)malloc(sizeof(char) * mainLength);

splitString(word, sameIndex, wordOne, wordTwo);

// Didn't used the wordOne, We just need substring.
free(wordOne);

return isContainsPhrase(branch.subBranches[a], wordTwo);
}
}

return 0;
}

int whichIndexInPhrase(Branch branch, char *word)
{
int *branchNumber = (int *)malloc(sizeof(int));
branchNumber[0] = getBranchNumber(branch);

for (int a = 0; a < branchNumber[0]; a++)
{
int sameIndex = compareForIndexes(word, branch.subBranches[a].value);

if (sameIndex == strlen(word))
{
// Going deeper to first branches

Branch *currentBranch = (Branch *)malloc(sizeof(Branch));
currentBranch[0] = branch.subBranches[a];

while (1)
{
if (getBranchNumber(currentBranch[0]) == 0)
{

// Going to parent and adding all values

char *newWord = (char *)malloc(sizeof(char) * mainLength);

while (currentBranch[0].value != key)
{
strcat(newWord, takeReversedString(currentBranch[0].value));
currentBranch = currentBranch->parentBranch;
}

strrev(newWord);

return mainLength - strlen(newWord);
}
else
{
currentBranch[0] = currentBranch[0].subBranches[0];
}
}
}
else if (sameIndex == strlen(branch.subBranches[a].value))
{
char *wordOne = (char *)malloc(sizeof(char) * mainLength);
char *wordTwo = (char *)malloc(sizeof(char) * mainLength);

splitString(word, sameIndex, wordOne, wordTwo);

// Didn't used the wordOne, We just need substring.
free(wordOne);

return whichIndexInPhrase(branch.subBranches[a], wordTwo);
}
}
}

int howManyForPhrase(Branch branch, char *word)
{
int *branchNumber = (int *)malloc(sizeof(int));
branchNumber[0] = getBranchNumber(branch);

for (int a = 0; a < branchNumber[0]; a++)
{
int sameIndex = compareForIndexes(word, branch.subBranches[a].value);

if (sameIndex == strlen(word))
{
// Going deeper to first branches
return findExtremeBranchNumber(branch.subBranches[a]);
}
else if (sameIndex == strlen(branch.subBranches[a].value))
{
char *wordOne = (char *)malloc(sizeof(char) * mainLength);
char *wordTwo = (char *)malloc(sizeof(char) * mainLength);

splitString(word, sameIndex, wordOne, wordTwo);

// Didn't used the wordOne, We just need substring.
free(wordOne);

return howManyForPhrase(branch.subBranches[a], wordTwo);
}
}
}

void lookForPhrase(Branch branch)
{
printf("Aramak istediginiz kelimeyi yazin:n");
char *searchingWord = (char *)malloc(sizeof(char) * mainLength);

scanf("%s", &searchingWord[0]);

if (isContainsPhrase(branch, searchingWord))
{
printf("nBu kelime obegi geciyor!n");
int *counter = (int *)malloc(sizeof(int));
counter[0] = 0;

int whichIndex = whichIndexInPhrase(branch, searchingWord);
printf("Gectigi indeks: %dn", whichIndex);

int howMany = howManyForPhrase(branch, searchingWord);
printf("Kac kere geciyor: %dn", howMany);
}
else
{
printf("nBu kelime obegi gecmiyor!n");
}
}

void main()
{
srand(time(NULL));

char *inputWord = takeString();
mainLength = strlen(inputWord);

if (!canBuildTree(inputWord))
{
printf("nBu kelime ile sonek agaci olusturalamiyor!n");
printf("Kelimenin sonuda $ eklemek ister misiniz? (y/n)n");
char answer;
scanf("%c", &answer);

if (answer == 'y')
{
mainLength++;
char *newInput = (char *)malloc(sizeof(char) * mainLength);
strcat(newInput, inputWord);
strcat(newInput, "$");

inputWord = newInput;
}
else
{
exit(1);
}
}

char **inputSuffixes = getSuffixes(inputWord);

Branch root = createBranch(key, mainLength, NULL);

printf("nrootn");
for (int a = 0; a < mainLength; a++)
{
addSuffixToBranch(root, inputSuffixes[a]);
}

printAll(root);

while (1)
{
printf("nn-----------------------nMenu:n");
printf("1 - Belirtilen alt katar geciyor mu, geciyorsa ilk bulundugu indeks kactir, kac kez tekrar etmektedir?n");
printf("2 - Tekrar eden en uzun altkatar nedir, kac kez tekrar etmektedir?n");
printf("3 - En cok tekrar eden alt katar nedir ve kac defa tekrar eder?n");
printf("4 - Cikisn");

int choice;
scanf("%d", &choice);

switch (choice)
{
case 1:
lookForPhrase(root);
break;
case 2:
printLongestPhrase(root);
break;
case 3:
printMostPhrase(root);
break;
case 4:
exit(0);
break;

default:
printf("Lutfen 1-4 arasi bir secim yapin.nn");
break;
}
}
}