Untitled
plain_text
2 months ago
5.1 kB
5
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; } } } }