A.前缀统计

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1000001;

int n ,m;
char a[N];
int idx = 1 ,cnt[N];
int ch[N][26];

void insert()
{
    int len = strlen(a + 1),u = 1;
    for (int i = 1; i <= len; i ++)
    {
        int x = a[i] - 'a';
        if (!ch[u][x]) ch[u][x] = ++ idx;
        u = ch[u][x];
    }
    cnt[u] ++;
}

int find()
{
    int res = 0;
    int len = strlen(a + 1),u = 1;
    for (int i = 1; i <= len; i ++)
    {
        int x = a[i] - 'a';
        if (!ch[u][x]) return res;
        u = ch[u][x];
        res += cnt[u];
    }
    return res;
}

int main()
{
    cin >> n >> m;
    while (n --)
    {
        cin >> a + 1;
        insert();
    }
    while (m -- )
    {
        cin >> a + 1;
        cout << find() << endl;
    }
    return 0;
}

B.最大异或对

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100001;

int n ,idx = 1; // 如果这里idx是0，则下面的所有u要从0开始
int a[N];
int ch[31 * N][2];

void insert(int x)
{
    int u = 1,len = 30;
    for (int i = len; i >= 0; i --)
    {
        int v = (x >> i) & 1;
        if (!ch[u][v]) ch[u][v] = ++ idx;
        u = ch[u][v];
    }
}

int find(int x)
{
    int res = 0;
    int u = 1,len = 30;
    for (int i = len; i >= 0; i --)
    {
        int v = (x >> i) & 1;
        if (ch[u][!v]) res = res * 2 + 1,u = ch[u][!v];
        else res = res * 2,u = ch[u][v];
    }
    return res;
}

int main()
{
    cin >> n;
    int res = 0;
    for (int i = 1; i <= n; i ++)
    {
        int x;
        cin >> x;
        insert(x);
        res = max(res , find(x));
    }
    cout << res;
    return 0;
}

C.最长异或路径

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1000001;

typedef long long LL;

int n;
int h[N] ,e[N] ,ne[N], idx;
LL w[N];
LL d[N];
bool vis[N];
int ch[N * 31][2] ,cnt;

void add(int a,int b,int c)
{
    e[idx] = b,w[idx] = c,ne[idx] = h[a],h[a] = idx ++;
}

void dfs(int x)
{
    for (int i = h[x]; ~i; i = ne[i])
    {
        int v = e[i];
        if (vis[v]) continue;
        vis[v] = true;
        d[v] = d[x] ^ w[i];
        dfs(v);
    }
}

void insert(LL x)
{
    int len = 30,u = 0;
    for (int i = len; i >= 0; i --)
    {
        int v = x >> i & 1;
        if (!ch[u][v]) ch[u][v] = ++ cnt;
        u = ch[u][v];
    }
}

LL find(LL x)
{
    int len = 30,u = 0;
    LL res = 0;
    for (int i = len; i >= 0; i --)
    {
        int v = x >> i & 1;
        if (ch[u][!v]) res = res * 2 + 1,u = ch[u][!v];
        else res = res * 2,u = ch[u][v];
    }
    return res;
}

int main()
{
    cin >> n;
    memset(h, -1, sizeof h);
    for (int i = 1; i < n; i++)
    {
        int a ,b ,c;
        cin >> a >> b >> c;
        add(a , b , c);
        add(b , a , c);
    }
    dfs(1); // 预处理出d数组：到1 ~ i节点的异或和

    LL res = 0;
    for (int i = 1; i <= n; i ++) // 变成最大异或和问题
    {
        insert(d[i]);
        res = max(res , find(d[i]));
    }

    cout << res;

    return 0;
}

E.单词拼接

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int M = 50500,N = 31;

int n ,idx = 1;
char a[M][N];
int ch[M * N][N];
bool e[M * N];

void insert(int cnt)
{
    int u = 1,len = strlen(a[cnt] + 1);
    for (int i = 1; i <= len; i ++)
    {
        int x = a[cnt][i] - 'a';
        if (!ch[u][x]) ch[u][x] = ++ idx;
        u = ch[u][x];
    }
    e[u] = true;
}

bool find(int l,int cnt,int num)
{
    int u = 1,len = strlen(a[cnt] + 1);
    if (l > len) return false;
    for (int i = l; i <= len; i++)
    {
        int x = a[cnt][i] - 'a';
        if (!ch[u][x]) return false;
        u = ch[u][x];
        if (e[u]) // 这要在往下走以后再判断
        {
            if (num == 1 && find(i + 1 , cnt , 2)) // 一个组成，递归再找一处
                return true;
            else if (num == 2 && i == len) return true;
        }
    }
    return false;
}

int main()
{
    n = 1;
    while (cin >> a[n] + 1)
    {
        insert(n);

        n ++;
    }
    n --;
    for (int i = 1; i <= n; i ++ )
        if (find(1 , i , 1))
            cout << a[i] + 1 << endl;
    return 0;
}

F.最短前缀

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1010,M = 31;

int n ,idx = 1;
char a[N][M];
int ch[N * M][M];
int vis[N * M];

void insert(int cnt)
{
    int u = 1,len = strlen(a[cnt] + 1);
    for (int i = 1; i <= len; i ++)
    {
        int x = a[cnt][i] - 'a';
        if (!ch[u][x]) ch[u][x] = ++ idx;
        u = ch[u][x];
        vis[u] ++;
    }
}

void find(int cnt)
{
    int u = 1,len = strlen(a[cnt] + 1);
    for (int i = 1; i <= len; i ++)
    {
        int x = a[cnt][i] - 'a';
        cout << a[cnt][i];
        u = ch[u][x];
        if (vis[u] == 1) break;
    }
    puts("");
}

int main()
{
    while (cin >> a[++ n] + 1)
        insert(n);

    for (int i = 1; i <= n; i ++ )
    {
        cout << a[i] + 1 << ' ';
        find(i);
    }
    return 0;
}