Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
2.9 kB
1
Indexable
Never
#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);
}