Untitled

 avatar
unknown
plain_text
a year ago
3.2 kB
4
Indexable
#include <iostream>
#include <string>
#define numAlphabet 26
using namespace std;      
 
int timeCounter; // helps for latest input time condition
 
struct wrd {
    string wordstr;     // word string
    int count, timing;  // most input and latest input time
};
 
struct wordProperties{
    wordProperties *childs[numAlphabet], *parent;
    bool isEndOfWord, isBanned;
    int freq, timing;
    wrd word;
 
    wordProperties(wordProperties* cur){
        for (int i=0; i<numAlphabet; i++) 
			childs[i] = NULL;
        parent = cur;
        isEndOfWord = false;
        word.wordstr = "";
        word.count = word.timing = freq = timing = 0;
        isBanned = false;
    }
} *root;

int mstrlen(const char str[])
{
    int ret = 0;
    while (str[ret]) ++ret;
    return ret;
}
 
void update(wordProperties *n, string str, int freq, int timing){
    while (n != NULL){
        if (n->word.count > freq) break;
        n->word.count = freq;
        n->word.wordstr = str;
        n->word.timing = timing;
        n = n->parent;
    }
}
 
void insert(char str[]){
    int len = mstrlen(str);
    wordProperties *temp = root;
    for (int i=0; i<len; i++){
        int index = str[i] - 'a';
        if (temp->childs[index] == NULL) 
			temp->childs[index] = new wordProperties(temp);
        temp = temp->childs[index];
    }
    temp->isEndOfWord = true;
    temp->freq++;
    temp->timing = timeCounter;
    // push the word in wordstr
    if (temp->isBanned != true) 
		update(temp, str, temp->freq, temp->timing);
}
 
string search(char str[20]){
    wordProperties *temp = root;
    int len = mstrlen(str);
    for (int i=0; i<len; i++){
        int index = str[i] - 'a';
        if (!temp->childs[index]) 
			return str;
        temp = temp->childs[index];
    }
    if (temp->word.count == 0) 
		return str;
    return temp->word.wordstr;
}
 
void init()
{
    timeCounter = 0;
    root = NULL;
    root = new wordProperties(root);
}
 
void inputWord(char mWord[20])
{
    timeCounter++;
    insert(mWord);
}
 
int recommend(char mUser[20], char mAnswer[20])
{
    string str = search(mUser);
    int size = str.size();
    str.copy(mAnswer, size);
    mAnswer[size] = '\0';
    return size;
}
 
void banWord(char mWord[20])
{
    wordProperties *temp = root;
    int len = mstrlen(mWord);
    for (int i=0; i<len; i++){
        int index = mWord[i] - 'a';
        if (temp->childs[index] == NULL) 
			temp->childs[index] = new wordProperties(temp);
        temp = temp->childs[index];
    }
    temp->isBanned = true;
     
    while (temp != NULL && temp->word.wordstr == mWord){
        temp->word.count = 0;
        for (int i=0; i<numAlphabet; i++){
            if (temp->childs[i] != NULL){
                if ((temp->childs[i]->word.count > temp->word.count) || (temp->childs[i]->word.count == temp->word.count)){
                    temp->word.count = temp->childs[i]->word.count;
                    temp->word.wordstr = temp->childs[i]->word.wordstr;
                    temp->word.timing = temp->childs[i]->word.timing;
                }
            }
        }
        temp = temp->parent;
    }
}
Editor is loading...
Leave a Comment