单链表

模板：

// head存储链表头，e[]存储节点的值，ne[]存储节点的next指针，idx表示当前用到了哪个节点
int head, e[N], ne[N], idx;
//此处head是第一个结点
// 初始化
void init()
{
    head = -1;
    idx = 0;
}

// 在链表头插入一个数x
void insert(int x)
{
    e[idx] = x, ne[idx] = head, head = idx ++ ;
}

// 将x插到下标是k的点后面
void add(int k, int x)
{
    e[idx] = x, ne[idx] = ne[k], ne[k] = idx, idx ++;
}

// 将下标是k的点后面的点删除
void remove (int k)
{
    ne[k] = ne[ne[k]];
}

// 将头结点删除，需要保证头结点存在
void remove()
{
    head = ne[head];
}

双链表

模板：

// e[]表示节点的值，l[]表示节点的左指针，r[]表示节点的右指针，idx表示当前用到了哪个节点
int e[N], l[N], r[N], idx;

// 初始化
void init()
{
    //0是左端点，1是右端点
    r[0] = 1, l[1] = 0;
    idx = 2;
}

// 在节点a的右边插入一个数x
void insert(int a, int x)
{
    e[idx] = x;
    l[idx] = a, r[idx] = r[a];
    l[r[a]] = idx, r[a] = idx ++ ;
}

// 删除节点a
void remove(int a)
{
    l[r[a]] = l[a];
    r[l[a]] = r[a];
}

模拟栈

// tt表示栈顶
int stk[N], tt = 0;

// 向栈顶插入一个数(加加减减)
stk[ ++ tt] = x;

// 从栈顶弹出一个数
tt -- ;

// 栈顶的值
stk[tt];

// 判断栈是否为空
cout << (tt ? "NO" : "YES") << endl;//tt > 0

应用：

表达式求值

模拟队列

普通队列：

// hh 表示队头，tt表示队尾
int q[N], hh = 0, tt = -1;

// 向队尾插入一个数
q[ ++ tt] = x;

// 从队头弹出一个数
hh ++ ;

// 队头的值
q[hh];

// 判断队列是否为空(hh <= tt)
cout << (hh <= tt ? "YES" : "NO");

循环队列

// hh 表示队头，tt表示队尾的后一个位置
//先存入再++
int q[N], hh = 0, tt = 0;

// 向队尾插入一个数
q[tt ++ ] = x;
if (tt == N) tt = 0;

// 从队头弹出一个数
hh ++ ;
if (hh == N) hh = 0;

// 队头的值
q[hh];

// 判断队列是否为空
if (hh != tt)
{

}

单调栈

常见模型：找出每个数左边离它最近的比它大/小的数

模板：

int tt = 0;
for (int i = 1; i <= n; i ++ )
{
    while (tt && check(stk[tt], i)) tt -- ;
    stk[ ++ tt] = i;
}

• 删掉栈中比x大的数

#include <iostream>

using namespace std;

const int N = 100010;

int stk[N], tt;

int main()
{
    int n;
    cin >> n;
    while (n -- )
    {
        int x;
        scanf("%d", &x);
        while (tt && stk[tt] >= x) tt -- ;
        if (!tt) printf("-1 ");
        else printf("%d ", stk[tt]);
        stk[ ++ tt] = x;
    }

    return 0;
}

单调队列

常见模型：找出滑动窗口中的最大值/最小值

int hh = 0, tt = -1;
for (int i = 0; i < n; i ++ )
{
    //q[tt]里存的是下标，便于和窗口长度的比较
    while (hh <= tt && check_out(q[hh])) hh ++ ;  // 判断队头是否滑出窗口
    while (hh <= tt && check(q[tt], i)) tt -- ;
    q[ ++ tt] = i;
}

• 单调队列:队列内的元素值是单调的，递增或递减。用单调队列存储当前窗口内单调递减的元素，并且队头是窗口内的最大值，队尾是窗口内的尾元素。也就是说，队列从队头到队尾对应窗口内从最大值到尾元素的一个子序列。
• 队头出队:当队头的元素从窗口滑出时，队头元素出队(hh++) ;
• 队尾入队:当新元素滑入窗口时，要把新元素从队尾插入，分两种情况:
  • 直接插入:如果新元素小于队尾元素，那就直接从队尾插入(++tt），因为它可能在前面的最大值滑出窗口后成为最大值;
  • 先删后插:如果新元素大于等于队尾元素，那就先删除队尾元素（因为它不可能成为窗口中的最大值)，删除方法是tt--，即从队尾出队。循环删除，直到队空或遇到一个大于新元素的值,插入其后(++tt)。

#include <iostream>

using namespace std;

const int N = 1000010;

int a[N], q[N];

int main()
{
    int n, k;
    scanf("%d%d", &n, &k);
    for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);

    int hh = 0, tt = -1;
    for (int i = 0; i < n; i ++ )
    {
        //q[hh]不在窗口[i - k + 1]内，队头出列
        if (hh <= tt && i - k + 1 > q[hh]) hh ++ ;

        while (hh <= tt && a[q[tt]] >= a[i]) tt -- ;//当前值>=队尾值，队尾出队
        q[ ++ tt] = i;//下标入队

        if (i >= k - 1) printf("%d ", a[q[hh]]);//队头最大值
    }

    puts("");

    hh = 0, tt = -1;
    for (int i = 0; i < n; i ++ )
    {
        if (hh <= tt && i - k + 1 > q[hh]) hh ++ ;

        while (hh <= tt && a[q[tt]] <= a[i]) tt -- ;
        q[ ++ tt] = i;

        if (i >= k - 1) printf("%d ", a[q[hh]]);
    }

    puts("");

    return 0;
}

KMP

暴力做法每次字符串向前移动一位从头比较，而kmp可以滑动一段距离而不是1，next数组是寻找当前位置的前缀和后缀相等的最大值

模板：

// s[]是长文本，p[]是模式串，n是s的长度，m是p的长度
求模式串的Next数组：

for (int i = 2, j = 0; i <= m; i ++ )//i = 1不用算
{
    while (j && p[i] != p[j + 1]) j = ne[j];
    if (p[i] == p[j + 1]) j ++ ;
    ne[i] = j;
}

// 匹配
for (int i = 1, j = 0; i <= n; i ++ )//i和j + 1 匹配，j和i要错一位
{
    while (j && s[i] != p[j + 1]) j = ne[j];//如果是暴力做法j直接变成0，kmp使j变成next数组的位置
    if (s[i] == p[j + 1]) j ++ ;//当前元素匹配，j移向p串下一位
    if (j == m)
    {
        j = ne[j];//继续匹配下一个字符串
        // 匹配成功后的逻辑
    }
}

trie树

高效地存储和查找字符串集合的数据结构

模板：

int son[N][26], cnt[N], idx;
// 0号点既是根节点，又是空节点
// son[][]存储树中每个节点的子节点
// cnt[]存储以每个节点结尾的单词数量

// 插入一个字符串
void insert(char *str)
{
    int p = 0;//根节点最开始是0
    for (int i = 0; str[i]; i ++ )
    {
        int u = str[i] - 'a';
        if (!son[p][u]) son[p][u] = ++ idx;//如果结点不存在，创建
        p = son[p][u];//让p变成最后一个结点
    }
    cnt[p] ++ ;//以这个结点为尾的单词数加一
}

// 查询字符串出现的次数
int query(char *str)
{
    int p = 0;
    for (int i = 0; str[i]; i ++ )
    {
        int u = str[i] - 'a';
        if (!son[p][u]) return 0;
        p = son[p][u];
    }
    return cnt[p];//返回p结点单词数量
}

应用：

最大异或对

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010, M = 3100010;

int n;
int a[N], son[M][2], idx;

void insert(int x)
{
    int p = 0;
    for (int i = 30; i >= 0; i -- )//从最高位开始找
    {
        int &s = son[p][x >> i & 1];//取x的第i位二进制
        if (!s) s = ++ idx;//不存在则创建新节点
        p = s;//指向下一层
    }
}

int search(int x)
{
    int p = 0, res = 0;
    for (int i = 30; i >= 0; i -- )
    {
        int s = x >> i & 1;
        if (son[p][!s])
        {
            res += 1 << i;
            /*如果当前子树中，存在第 i位和 x 的第i位不同的数，
            说明答案的第 i 位可以变成1，就把 res 的第 i 位二进制位变成1。
            如果存在和x的第i位不同的数，则这一位可以变成1，否则只能是0。和x的第i位具体是几无关。*/
            p = son[p][!s];
        }
        else p = son[p][s];
    }
    return res;
}

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ )
    {
        scanf("%d", &a[i]);
        insert(a[i]);
    }

    int res = 0;
    for (int i = 0; i < n; i ++ ) res = max(res, search(a[i]));

    printf("%d\n", res);

    return 0;
}