算法

(构造) $O(n)$

先初始化字符串s，即在100个位置上置为 'a' ，把这个字符串作为s[0]输出即可，然后遍历$lcp$数组里的每个元素x，判断s[x]是否为'a'，若是，则把s[x]置为'b'，否则置为'a'即可，并输出该字符串。

C++ 代码

#include <iostream>

using namespace std;

int main() {
    int t;
    cin >> t;

    while (t--) {
        int n;
        cin >> n;
        string s(100, 'a');
        cout << s << '\n';
        for (int i = 0, x; i < n; ++i) {
            cin >> x;
            if (s[x] == 'a') s[x] = 'b';
            else s[x] = 'a';
            cout << s << '\n';
        }
    }

    return 0;
}