Untitled
unknown
plain_text
2 years ago
2.9 kB
4
Indexable
#include <stdio.h> struct strNode { strNode *merged; strNode *next; strNode *prev; int iStr[12]; // extract int's instead of string literal's and hold it int deathTime; }; strNode X[20000]; // 26*26*26 = 17576 =~ 20,000 strNode *wordTrie[26][26][26];// trie data structure for 3 char's int inSize; int maxStrLen; // lined list to hold live items struct linkedlist { strNode *head; strNode *tail; } LiveItems; void init(int N) { maxStrLen = N; register long long int *initword = (long long int *)wordTrie; for (register int i = 0; i < 17576/*26*3*/; i++) initword[i] = 0; inSize = 0; LiveItems.head = &X[inSize++]; LiveItems.tail = &X[inSize++]; LiveItems.head->next = LiveItems.tail; LiveItems.tail->prev = LiveItems.head; } //This function returns the number of living strings whose length is mLen at mTimestamp int checkString(int mTimestamp, int mLen) { register int ans = 0; for (register strNode *now = LiveItems.head->next; now != LiveItems.tail;) { if (!now->merged && now->deathTime > mTimestamp) { ans += now->iStr[mLen]; now = now->next; } else { now->prev->next = now->next; now->next->prev = now->prev; now = now->next; } } return ans; } int generateString(int mTimestamp, int mLifespan, int mLen, register char *mStr) { register strNode *now = &X[inSize++]; now->deathTime = mTimestamp + mLifespan; now->merged = 0;//initiliaze struct with 0 / null pointer for (register int i = 0; i < mLen; i++) mStr[i] -= 'a'; for (register int i = 1; i <= maxStrLen; i++) now->iStr[i] = 0; now->iStr[mLen] = 1; now->prev = LiveItems.tail->prev; now->next = LiveItems.tail; LiveItems.tail->prev->next = now; LiveItems.tail->prev = now; for (register int i = 0; i < mLen - 2; i++) { register strNode **word_now = &wordTrie[mStr[i]][mStr[i + 1]][mStr[i + 2]]; register strNode *check = *word_now; if (check) { while (check->merged) check = check->merged; if (check->deathTime <= mTimestamp) *word_now = now; else if (check != now) { *word_now = now; for (register int i = 1; i <= maxStrLen; i++) now->iStr[i] += check->iStr[i]; check->merged = now; check->prev->next = check->next; check->next->prev = check->prev; } } else *word_now = now; } return checkString(mTimestamp, mLen); }
Editor is loading...