Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
2.4 kB
1
Indexable
Never
struct str
{
    str *merged, *next, *prev;
    int wordnum[12], expire;
} X[20000];
str *word[26][26][26];
int wordset, gN;
 
struct linkedlist
{
    str *head, *tail;
} survive;
 
void init(int N)
{
    gN = N;
    register long long int *initword = (long long int *)word;
    for (register int i = 0; i < 17576; i++)
        initword[i] = 0;
 
    wordset = 0;
    survive.head = &X[wordset++];
    survive.tail = &X[wordset++];
 
    survive.head->next = survive.tail;
    survive.tail->prev = survive.head;
}
 
int checkString(int mTimestamp, int mLen)
{
    register int ans = 0;
 
    for (register str *now = survive.head->next; now != survive.tail;)
    {
        if (!now->merged && now->expire > mTimestamp)
        {
            ans += now->wordnum[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 str *now = &X[wordset++];
    now->expire = mTimestamp + mLifespan;
    now->merged = 0;
    for (register int i = 0; i < mLen; i++)
        mStr[i] -= 'a';
    for (register int i = 1; i <= gN; i++)
        now->wordnum[i] = 0;
 
    now->wordnum[mLen] = 1;
 
    now->prev = survive.tail->prev;
    now->next = survive.tail;
 
    survive.tail->prev->next = now;
    survive.tail->prev = now;
 
    for (register int i = 0; i < mLen - 2; i++)
    {
        register str **word_now = &word[mStr[i]][mStr[i + 1]][mStr[i + 2]];
        register str *check = *word_now;
        if (check)
        {
            while (check->merged)
                check = check->merged;
            if (check->expire <= mTimestamp)
                *word_now = now;
            else if (check != now)
            {
                *word_now = now;
                for (register int i = 1; i <= gN; i++)
                    now->wordnum[i] += check->wordnum[i];
                check->merged = now;
                check->prev->next = check->next;
                check->next->prev = check->prev;
            }
        }
        else
            *word_now = now;
    }
 
    return checkString(mTimestamp, mLen);
}