Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
5.1 kB
6
Indexable
Never
#define     FAST        __attribute((optimize("Ofast")))
 
FAST void mstrcpy(char dst[], const char src[])
{
    int c = 0;
    while ((dst[c] = src[c]) != 0)
        ++c;
}
 
FAST int mstrlen(const char str[])
{
    int ret = 0;
    while (str[ret])
        ++ret;
    return ret;
}
 
FAST int mstrcmp(const char str1[], const char str2[])
{
    int c = 0;
    while (str1[c] != 0 && str1[c] == str2[c])
        ++c;
    return str1[c] - str2[c];
}
 
#define rint register int
 
struct trie_node
{
    int childs[26];
    int ban;
    int dataindex;
    int recommendindex;
} nodes[650000];
 
struct data
{
    int count;
    int timestamp;
    char t[20];
} data[25000];
 
int nodecount;
int datacount;
int root;
int timeline;
 
FAST int getnewnode()
{
    trie_node *p = &nodes[++nodecount];
    for (rint i = 0; i < 26; i++) p->childs[i] = -1;
    p->ban = 0;
    p->dataindex = -1;
    p->recommendindex = -1;
    return nodecount;
}
 
FAST void init()
{
    nodecount = -1;
    datacount = 0;
    root = getnewnode();
    timeline = 0;
}
 
FAST void updaterecommend(int dindex, char s[])
{
    int tmproot = root;
    char *p = s;
    while (1)
    {
        if (!nodes[tmproot].ban)
        {
            int m = nodes[tmproot].recommendindex;
            if (m == -1)
            {
                nodes[tmproot].recommendindex = dindex;
            }
            else
            {
                if (data[m].count < data[dindex].count)
                {
                    nodes[tmproot].recommendindex = dindex;
                }
                else if (data[m].count == data[dindex].count)
                {
                    if (data[m].timestamp < data[dindex].timestamp)
                    {
                        nodes[tmproot].recommendindex = dindex;
                    }
                }
            }
        }
        if (*p == '\0') break;
        tmproot = nodes[tmproot].childs[*p - 'a'];
        p++;
    }
}
 
FAST void inputWord(char mWord[20])
{
    int tmproot = root;
    char *p = mWord;
    while (*p != '\0')
    {
        if (nodes[tmproot].childs[*p - 'a'] == -1)
        {
            nodes[tmproot].childs[*p - 'a'] = getnewnode();
        }
        tmproot = nodes[tmproot].childs[*p - 'a'];
        p++;
    }
    timeline++;
 
    if (!nodes[tmproot].ban)
    {
        if (nodes[tmproot].dataindex != -1)
        {
            data[nodes[tmproot].dataindex].count++;
            data[nodes[tmproot].dataindex].timestamp = timeline;
        }
        else
        {
            data[datacount].count = 1;
            data[datacount].timestamp = timeline;
            nodes[tmproot].dataindex = datacount;
            mstrcpy(data[datacount].t, mWord);
            datacount++;
        }
        updaterecommend(nodes[tmproot].dataindex, mWord);
    }
}
 
FAST int recommend(char mUser[20], char mAnswer[20])
{
    int tmproot = root;
    char *p = mUser;
    while (*p != '\0')
    {
        if (nodes[tmproot].childs[*p - 'a'] == -1)
        {
            mstrcpy(mAnswer, mUser);
            return mstrlen(mUser);
        }
        tmproot = nodes[tmproot].childs[*p - 'a'];
        p++;
    }
 
    if (nodes[tmproot].recommendindex != -1)
        mstrcpy(mAnswer, data[nodes[tmproot].recommendindex].t);
    else
        mstrcpy(mAnswer, mUser);
    return mstrlen(mAnswer);
}
 
FAST void banWord(char mWord[20])
{
    int tmproot = root;
    int len = 0;
    int path[20] = { 0 };
    while (*mWord != '\0')
    {
        if (nodes[tmproot].childs[*mWord - 'a'] == -1)
        {
            nodes[tmproot].childs[*mWord - 'a'] = getnewnode();
        }
        path[len] = tmproot;
        tmproot = nodes[tmproot].childs[*mWord - 'a'];
        mWord++; len++;
    }
    nodes[tmproot].ban = 1;
 
    if (nodes[tmproot].dataindex != -1)
    {
        for (rint i = len - 1; i >= 0; i--)
        {
            int t = 0;
            int c = 0;
            int r = -1;
            if (nodes[path[i]].recommendindex == nodes[tmproot].dataindex)
            {
                for (rint j = 0; j < 26; j++)
                {
                    int m = nodes[path[i]].childs[j];
                    int mi = nodes[m].recommendindex;
                    if ((m != -1) && (!nodes[m].ban) && (mi != -1))
                    {
                        if (data[mi].count > c)
                        {
                            c = data[mi].count;
                            r = nodes[m].recommendindex;
                        }
                        else if (data[mi].count == c)
                        {
                            if (data[mi].timestamp > t)
                            {
                                t = data[mi].timestamp;
                                r = nodes[m].recommendindex;
                            }
                        }
                    }
                }
                nodes[path[i]].recommendindex = r;
            }
        }
    }
}