题解：文本编辑器

一、题目分析

本题要求实现一个文本编辑器，该编辑器由一段文本和一个光标组成，支持移动光标、插入字符、删除字符、获取字符以及光标前后移动等操作。

二、解题思路

本题采用块状链表来实现文本编辑器。块状链表是一种将多个元素存储在一个节点中的链表结构，这里每个节点存储一个长度不超过N的字符数组，通过这种方式来优化插入、删除等操作的时间复杂度。

（一）数据结构定义

const int N = 2000, M = 2010;
int n, x, y;
struct Node
{
    char s[N + 1];
    int c, l, r;
}p[M];
char str[2000010];
int q[M], tt; 

• N：定义每个节点存储字符数组的最大长度。
• M：定义节点的最大数量。
• n：存储操作的数量。
• x：表示当前光标所在节点的编号。
• y：表示光标在当前节点内的位置。
• Node结构体：表示块状链表的节点，包含字符数组s（存储字符）、字符数量c、左节点编号l和右节点编号r。
• str：字符数组，用于临时存储插入的字符串。
• q和tt：q数组用于内存回收，tt是数组下标，指向当前可回收节点的位置。

（二）光标移动函数move

void move(int k)  
{
    x = p[0].r;
    while (k > p[x].c) k -= p[x].c, x = p[x].r;
    y = k - 1;
}

将光标移动到第k个字符之后。从链表头开始遍历，找到光标所在的节点x，并确定光标在该节点内的位置y。

（三）节点插入函数add

void add(int x, int u)  
{
    p[u].r = p[x].r, p[p[u].r].l = u;
    p[x].r = u, p[u].l = x;
}

将节点u插到节点x的右边，更新节点的左右指针关系。

（四）节点删除函数del

void del(int u)  
{
    p[p[u].l].r = p[u].r;
    p[p[u].r].l = p[u].l;
    p[u].l = p[u].r = p[u].c = 0; 
    q[ ++ tt] = u; 
}

删除节点u，更新其相邻节点的指针关系，清空节点u的信息，并将其加入到回收队列中。

（五）插入操作函数insert

void insert(int k)  
{
    if (y < p[x].c - 1)  
    {
        int u = q[tt -- ];  
        for (int i = y + 1; i < p[x].c; i ++ )
            p[u].s[p[u].c ++ ] = p[x].s[i];
        p[x].c = y + 1;
        add(x, u);
    }
    int cur = x;
    for (int i = 0; i < k;)
    {
        int u = q[tt -- ];  
        while (p[u].c < N && i < k)
            p[u].s[p[u].c ++ ] = str[i ++ ];
        add(cur, u);
        cur = u;
    }
}

在光标后插入k个字符。如果光标不在当前节点末尾，先将当前节点从光标处分裂；然后创建新节点，将插入的字符存储到新节点中，并插入到链表中。

（六）删除操作函数remove

void remove(int k)  
{
    if (p[x].c - 1 - y >= k)  
    {
        for (int i = y + k + 1, j = y + 1; i < p[x].c; i ++, j ++ ) p[x].s[j] = p[x].s[i];
        p[x].c -= k;
    }
    else
    {
        k -= p[x].c - y - 1; 
        p[x].c = y + 1;
        while (p[x].r && k >= p[p[x].r].c)
        {
            int u = p[x].r;
            k -= p[u].c;
            del(u);
        }
        int u = p[x].r; 
        for (int i = 0, j = k; j < p[u].c; i ++, j ++ ) p[u].s[i] = p[u].s[j];
        p[u].c -= k;
    }
}

删除光标后的k个字符。如果当前节点内可删除的字符数大于等于k，直接在当前节点内删除；否则，先删除当前节点的剩余部分，再依次删除后续节点，直到删除k个字符。

（七）获取字符函数get

void get(int k)  
{
    if (p[x].c - 1 - y >= k)  
    {
        for (int i = 0, j = y + 1; i < k; i ++, j ++ ) putchar(p[x].s[j]);
    }
    else
    {
        k -= p[x].c - y - 1;
        for (int i = y + 1; i < p[x].c; i ++ ) putchar(p[x].s[i]); 
        int cur = x;
        while (p[cur].r && k >= p[p[cur].r].c)
        {
            int u = p[cur].r;
            for (int i = 0; i < p[u].c; i ++ ) putchar(p[u].s[i]);
            k -= p[u].c;
            cur = u;
        }
        int u = p[cur].r;
        for (int i = 0; i < k; i ++ ) putchar(p[u].s[i]);
    }
    puts("");
}

输出光标后的k个字符。如果当前节点内可输出的字符数大于等于k，直接在当前节点内输出；否则，先输出当前节点的剩余部分，再依次输出后续节点的字符，直到输出k个字符。

（八）光标前移函数prev

void prev()  
{
    if (!y)
    {
        x = p[x].l;
        y = p[x].c - 1;
    }
    else y -- ;
}

将光标向前移动一位。如果光标在当前节点开头，则移动到前一个节点的末尾；否则，在当前节点内向前移动一位。

（九）光标后移函数next

void next()  
{
    if (y < p[x].c - 1) y ++ ;
    else
    {
        x = p[x].r;
        y = 0;
    }
}

将光标向后移动一位。如果光标不在当前节点末尾，则在当前节点内向后移动一位；否则，移动到下一个节点的开头。

（十）节点合并函数merge

void merge()  
{
    for (int i = p[0].r; i; i = p[i].r)
    {
        while (p[i].r && p[i].c + p[p[i].r].c < N)
        {
            int r = p[i].r;
            for (int j = p[i].c, k = 0; k < p[r].c; j ++, k ++ )
                p[i].s[j] = p[r].s[k];
            if (x == r) x = i, y += p[i].c; 
            p[i].c += p[r].c;
            del(r);
        }
    }
}

将长度较短的相邻节点合并，以保证块状链表的时间复杂度。遍历链表，将相邻且字符总数小于N的节点合并。

（十一）主函数main

int main()
{
    for (int i = 1; i < M; i ++ ) q[ ++ tt] = i;
    scanf("%d", &n);
    char op[10];

    str[0] = '>';
    insert(1);  
    move(1);  

    while (n -- )
    {
        int a;
        scanf("%s", op);
        if (!strcmp(op, "Move"))
        {
            scanf("%d", &a);
            move(a + 1);
        }
        else if (!strcmp(op, "Insert"))
        {
            scanf("%d", &a);
            int i = 0, k = a;
            while (a)
            {
                str[i] = getchar();
                if (str[i] >= 32 && str[i] <= 126) i ++, a -- ;
            }
            insert(k);
            merge();
        }
        else if (!strcmp(op, "Delete"))
        {
            scanf("%d", &a);
            remove(a);
            merge();
        }
        else if (!strcmp(op, "Get"))
        {
            scanf("%d", &a);
            get(a);
        }
        else if (!strcmp(op, "Prev")) prev();
        else next();
    }

    return 0;
}

1. 初始化回收队列q，读取操作数量n。
2. 插入一个哨兵节点，并将光标移动到哨兵节点后面。
3. 循环处理每个操作：
   • 如果是Move操作，调用move函数移动光标。
   • 如果是Insert操作，读取插入字符的数量，获取要插入的字符串，调用insert函数插入字符，然后调用merge函数合并节点。
   • 如果是Delete操作，读取删除字符的数量，调用remove函数删除字符，然后调用merge函数合并节点。
   • 如果是Get操作，读取获取字符的数量，调用get函数输出字符。
   • 如果是Prev操作，调用prev函数将光标前移。
   • 如果是Next操作，调用next函数将光标后移。

四、时间复杂度和空间复杂度

（一）时间复杂度

• 初始化操作：时间复杂度为(O(1))。
• 移动光标操作：遍历链表找到光标位置，时间复杂度为(O(n / N))，其中n是文本长度，N是每个节点存储字符的最大数量。
• 插入操作：插入字符和分裂节点的时间复杂度为(O(k / N))，k是插入字符的数量；合并节点的时间复杂度为(O(n / N))，所以插入操作的总时间复杂度为(O((k + n) / N))。
• 删除操作：删除字符和处理节点的时间复杂度为(O(k / N))，合并节点的时间复杂度为(O(n / N))，所以删除操作的总时间复杂度为(O((k + n) / N))。
• 获取字符操作：获取字符的时间复杂度为(O(k / N))。
• 光标前后移动操作：时间复杂度为(O(1))。
• 总的时间复杂度为(O(m \times (n + k) / N))，其中m是操作的数量。

（二）空间复杂度

需要存储块状链表的节点p[M]、临时字符串str以及回收队列q[M]，空间复杂度为(O(M + n))，近似为(O(n))。