思路

1. 模式串（小的）匹配失败的时候，不会全部回退，而是回退到最近一次可以落脚的地方

   比如我们有个模式串（小的）ababc，那么当我匹配到c失败的时候，我可以将模式串下标(j)回退到初始位置，然后字符串下标回退到开始匹配的起点的下一个位置（无法理解可以模拟一下暴力过程）

   但是此时，abab这个东西就会引起我们的注意，既然是在c的位置出的问题，就表明前面的完全没问题，那假设我们仅仅向后挪动一个，那么下次匹配的就是b和a进行比较，必定失败。我们将模式串看作钥匙，带齿的，每个字母代替一种高度，当abab匹配完成的时候，我们已经可以看到它的大致形状，像玩游戏一样，我们如果能看到钥匙的形状，那么一定会主动向后挪动两个位置，即让a1b1放到a2b2的位置。如果我们的模式串是abababababc呢，我们会主动向后移动8个位置。

   同时，向后移动并不是仅仅为了寻找有效地址，而是因为到c的时候，向后移动模式串，此时无法匹配钥匙形状的位置，是没有希望的，前途黑暗的，因为后路被自己就封死了。

   大概就这么个意思，思路还是很简单的，主要的代码简短，比较抽象

Debug

1. 边界，两层while都要控制i的边界，不然内层会爆掉i
2. 输出判断，当内层i>m时，会出循环，但是此时会输出，与预测不符；真正符合输出的是j读到结尾，即

    if (j > n)
    {
        cout << ;
    }

代码

#include <iostream>
#include <cstring>

using namespace std;

const int N = 1e5 + 10;
const int M = 1e6 + 10;

char p[N];
char s[M];
int nxt[N];

void kmp(int n, int m)
{
    nxt[1] = 0;
    int i, k, j;
    i = 1;
    k = 0;

    while (i <= n)
    {
        if (!k || p[i] == p[k]) nxt[++i] = ++k;
        else k = nxt[k];
    }

    i = j = 1;

    while (i <= m)
    {
        while (j <= n && i <= m) {
            if (!j || p[j] == s[i]) ++i, ++j;
            else j = nxt[j];
        }
        if (j > n)
        {
            cout << i - j << " ";
            j = nxt[j];
        }
    }

    return ;
}

int main()
{
    int n, m;

    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> p[i];
    }

    cin >> m;
    for (int i = 1; i <= m; i++)
    {
        cin >> s[i];
    }

    kmp(n, m);

}

/*
100
nNNNNNNNgUUUUULLLLLL44UU88888sNNNN5gfffvvvvvvvvv77nNONNNNNgUUUUUkLLLLL44Ui88888sNNNN5gfAfvvvSvvvvv7x
500
nNNNNNNNgUUUUULLLLLL44UU88888sNNNN5gfffvvvvvvvvv77nNONNNNNgUUUUUkLLLLL44Ui88888sNNNN5gfAfvvvSvvvvv7xnNNNNNNNgUUUUULLLLLL44UU88888sNNNN5gfffvvvvvvvvv77nNONNNNNgUUUUUkLLLLL44Ui88888sNNNN5gfAfvvvSvvvvv7xnNA6fQNNluS6Uo12Lhd2UMUVm8bd6xNhNNyg1SNvvKvavJGn77RNjqBNNNg2UUUfkLLLs8Q47B85u8jrNeNNqWxAzvB9Sgv9vBfxnNNNNNNNgUUUUULLLLLL44UU88888sNNNN5gfffvvvvvvvvv77nNONNNNNgUUUUUkLLLLL44Ui88888sNNNN5gfAfvvvSvvvvv7xnNVF3NVsgUOUUxjULxAU44PU788P8se0LNpSfffvvkvvvnKyosnNEN2KNNgU3OUxkLuLLx44vixt08OsNNNN5ZtAfvOvsvivpv72

0 100 300
*/

/*
10
jNNNNjNNNN
30
jNNPw9NNNNnNMANTNHGNjNNNNjNNNN

20
*/

#include <iostream>
#include <cstring>

using namespace std;

const int N = 1e5 + 10;
const int M = 1e6 + 10;

char p[N];
char s[M];
int nxt[N];

void kmp(int n, int m)
{
    nxt[1] = 0;
    int i, k, j;
    i = 1;
    k = 0;

    while (i <= n)
    {
        if (!k || p[i] == p[k]) nxt[++i] = ++k;
        else k = nxt[k];
    }

    i = j = 1;

    while (i <= m)
    {
        while (j <= n && i <= m) {
            if (!j || p[j] == s[i]) ++i, ++j;
            else j = nxt[j];
        }
        if (j > n)
        {
            cout << i - j << " ";
            j = nxt[j];
        }
    }

    return ;
}

int main()
{
    int n, m;

    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> p[i];
    }

    cin >> m;
    for (int i = 1; i <= m; i++)
    {
        cin >> s[i];
    }

    kmp(n, m);

}

/*
100
nNNNNNNNgUUUUULLLLLL44UU88888sNNNN5gfffvvvvvvvvv77nNONNNNNgUUUUUkLLLLL44Ui88888sNNNN5gfAfvvvSvvvvv7x
500
nNNNNNNNgUUUUULLLLLL44UU88888sNNNN5gfffvvvvvvvvv77nNONNNNNgUUUUUkLLLLL44Ui88888sNNNN5gfAfvvvSvvvvv7xnNNNNNNNgUUUUULLLLLL44UU88888sNNNN5gfffvvvvvvvvv77nNONNNNNgUUUUUkLLLLL44Ui88888sNNNN5gfAfvvvSvvvvv7xnNA6fQNNluS6Uo12Lhd2UMUVm8bd6xNhNNyg1SNvvKvavJGn77RNjqBNNNg2UUUfkLLLs8Q47B85u8jrNeNNqWxAzvB9Sgv9vBfxnNNNNNNNgUUUUULLLLLL44UU88888sNNNN5gfffvvvvvvvvv77nNONNNNNgUUUUUkLLLLL44Ui88888sNNNN5gfAfvvvSvvvvv7xnNVF3NVsgUOUUxjULxAU44PU788P8se0LNpSfffvvkvvvnKyosnNEN2KNNgU3OUxkLuLLx44vixt08OsNNNN5ZtAfvOvsvivpv72

0 100 300
*/

/*
10
jNNNNjNNNN
30
jNNPw9NNNNnNMANTNHGNjNNNNjNNNN

20
*/

思路

1. 维护两个单调队列
2. 最大值：只要大的，小的不要，所以遇到比自己小的就删掉（出栈），rr--;
3. 最小值：只要小的，大的不要，所以遇到比自己大的就删掉（出栈），rr--;
4. 如何维护窗口边界
   • 左边界用i-k+1和当前存储的单调队列左边界相比较，如果单调队列不在窗口内了，ll++，因为是一个一个读的，所以边界判断一次即可
   • 单调队列怎么定义的
     • 这里跟y总定义的一样，单调队列的左边界为最值，以最小值举例，最小的一定在最左边
     • 有没有可能中间出现一个最小的，可能，此时就会将原来的左边界吞掉，也就是rr--，因为最值需要一个就够了，
     • 单调队列会不有3 1 2的情况出现，不会，因为读到2之前，1就会把3吞掉
   • 右边界就是rr维护，通常用不到维护，因为单调栈的右边界<=窗口的右边界（都是i顺着读的，总不能超出去）

注意

1. 输出的时候i>=k-1 的时候才开始输出
2. 最大最小改个符号
3. 注意更新的时候等号的处理，这里等号应该是留下的

代码

#include <iostream>
#include <cstring>
using namespace std;

const int N = 1e6 + 10;

int a[N], ind[N];

int n, k;

int main ()
{
    cin >> n >> k;

    for (int i = 0; i < n; i ++) 
    {
        cin >> a[i];
    }

    int ll, rr;
    ll = rr = 0;
    for (int i = 0; i < n; i ++) 
    {
        if (ll < rr && ind[ll] < i-k+1) ll ++;
        while (ll < rr && a[i] < a[ind[rr-1]]) rr --;
        ind[rr++] = i;

        if (i >= k-1)
            cout << a[ind[ll]] << " ";
    }

    cout << endl;
    memset(ind, 0, sizeof ind);

    ll = rr = 0;
    for (int i = 0; i < n; i ++)
    {
        if (ll < rr && ind[ll] < i-k+1) ll ++;
        while (ll < rr && a[i] > a[ind[rr-1]]) rr --;
        ind[rr++] = i;

        if (i >= k-1)
            cout << a[ind[ll]] << " ";
    }

    cout << endl;

    return 0;
}

#include <iostream>
#include <cstring>
using namespace std;

const int N = 1e6 + 10;

int a[N], ind[N];

int n, k;

int main ()
{
    cin >> n >> k;

    for (int i = 0; i < n; i ++) 
    {
        cin >> a[i];
    }

    int ll, rr;
    ll = rr = 0;
    for (int i = 0; i < n; i ++) 
    {
        if (ll < rr && ind[ll] < i-k+1) ll ++;
        while (ll < rr && a[i] < a[ind[rr-1]]) rr --;
        ind[rr++] = i;

        if (i >= k-1)
            cout << a[ind[ll]] << " ";
    }

    cout << endl;
    memset(ind, 0, sizeof ind);

    ll = rr = 0;
    for (int i = 0; i < n; i ++)
    {
        if (ll < rr && ind[ll] < i-k+1) ll ++;
        while (ll < rr && a[i] > a[ind[rr-1]]) rr --;
        ind[rr++] = i;

        if (i >= k-1)
            cout << a[ind[ll]] << " ";
    }

    cout << endl;

    return 0;
}

思路

• 暴力循环

注意

• 题目给的条件是小于，所以大于等于分一类，注意区分等号情况的位置

#include <iostream>

using namespace std;

const int N = 1e5;

int a[N];
int b[N];

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

    for (int i = 1; i <= n; i ++)
    {
        cin >> a[i];
    }

    a[0] = -1;
    for (int i = 1; i <= n;  i ++)
    {
        int t = i-1;
        if (a[i] > a[t])
        {
            b[i] = a[t];
        }
        else 
        {
            while(a[i] <= b[t])
            {
                t --;
            }
            b[i] = b[t];
        }
    }

    for (int i = 1; i <= n; i ++)
    {
        cout << b[i] << " ";
    }
    cout << endl;

    return 0;

}

/*
10
11 27 11 6 14 26 8 22 13 7 

-1 11 -1 -1 6 14 6 8 8 6 
-1 11 11 -1 6 14 6 8 8 6 
*/

#include <iostream>

using namespace std;

const int N = 1e5;

int a[N];
int b[N];

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

    for (int i = 1; i <= n; i ++)
    {
        cin >> a[i];
    }

    a[0] = -1;
    for (int i = 1; i <= n;  i ++)
    {
        int t = i-1;
        if (a[i] > a[t])
        {
            b[i] = a[t];
        }
        else 
        {
            while(a[i] <= b[t])
            {
                t --;
            }
            b[i] = b[t];
        }
    }

    for (int i = 1; i <= n; i ++)
    {
        cout << b[i] << " ";
    }
    cout << endl;

    return 0;

}

/*
10
11 27 11 6 14 26 8 22 13 7 

-1 11 -1 -1 6 14 6 8 8 6 
-1 11 11 -1 6 14 6 8 8 6 
*/

思路

1. 带头结点的单链表
2. HEAD指向队头，即push在队尾，pop在队头

注意

1. 操作头结点的时候，要新建一个指针，初始的指针不能动，不然后面就乱套了
2. 赋值temp的时候，要先在NULL的位置new一下，然后再更改，因为NULL的时候赋值没有指针关联关系，相当于赋值成了野指针

    // Right
    head->next = new();
    temp = head->next;

    // Wrong
    temp = head->next;
    temp = new();

Debug

1. 注意pop和push的位置不一样，但一定有一个会while循环到结尾

代码

#include <iostream>
#include <cstring>

using namespace std;

typedef struct link
{
    link * next;
    int x;
}*LINK;

string s;
int t;

int main ()
{
    int n = 0;

    LINK head = new link;
    head->next = NULL;

    cin >> n;

    while (n > 0)
    {
        n --;
        cin >> s;
        if (s == "push")
        {
            cin >> t;
            LINK temp = head;
            while (temp->next)
            {
                temp = temp->next;      
            }
            temp->next = new link;
            temp = temp->next;
            temp->x = t;
            temp->next = NULL;
        }
        else if (s == "pop")
        {
            LINK temp = head->next;
            head->next = temp->next;
            delete(temp);
        }
        else if (s == "empty")
        {
            if (head->next == NULL)
            {
                cout <<"YES" << endl;
            }
            else 
            {
                cout << "NO" << endl;
            }
        }
        else if (s == "query")
        {
            cout << head->next->x << endl;
        }
    }

    return 0;
}

#include <iostream>
#include <cstring>

using namespace std;

typedef struct link
{
    link * next;
    int x;
}*LINK;

string s;
int t;

int main ()
{
    int n = 0;

    LINK head = new link;
    head->next = NULL;

    cin >> n;

    while (n > 0)
    {
        n --;
        cin >> s;
        if (s == "push")
        {
            cin >> t;
            LINK temp = head;
            while (temp->next)
            {
                temp = temp->next;      
            }
            temp->next = new link;
            temp = temp->next;
            temp->x = t;
            temp->next = NULL;
        }
        else if (s == "pop")
        {
            LINK temp = head->next;
            head->next = temp->next;
            delete(temp);
        }
        else if (s == "empty")
        {
            if (head->next == NULL)
            {
                cout <<"YES" << endl;
            }
            else 
            {
                cout << "NO" << endl;
            }
        }
        else if (s == "query")
        {
            cout << head->next->x << endl;
        }
    }

    return 0;
}

思路

很简单，就是维护数字和字符两个栈

1. 读到数字，放入
2. 读到字符，
   • 字符等级高，直接放入
   • 字符等级低，则把前面高的全都eval一遍（此时注意while循环需要加上op.size()判断），然后放入
3. 读到左括号，放入，等待右括号

4. 读到右括号，循环计算，直到读到左括号

   • 计算之后需要手动弹出左括号

5. eval函数比较好理解，就是挑左右两个数和一个运算符

   • 由于栈是动态维护的且遵循读入的顺序，所以只要存入弹出没有问题，那么配对计算是没有问题的

注意点

1. 所有的弹出操作都在eval中进行，所以主干不需要维护出栈
   • 除了（，需要在主程序中弹出，因为不会进入到eval中
2. while的时候要加上op.size()的判断，不然会SE

代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <stack>
#include <unordered_map>

using namespace std;

unordered_map<char, int> h {{'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}};
stack<int> num;
stack<char> op;

void eval()
{
    int b = num.top();
    num.pop();

    int a = num.top();
    num.pop();

    char c = op.top();
    op.pop();

    int x = 0;
    if (c == '+') x = a + b;
    else if (c == '-') x = a - b;
    else if (c == '*') x = a*b;
    else if (c == '/') x = a/b;

    num.push(x);

    return ;
}

int main ()
{
    string s;
    cin >> s;

    for (int i = 0; i < s.size(); i ++)
    {
        if (isdigit(s[i]))
        {
            int x = 0;
            int j = i;
            while (isdigit(s[j]))
            {
                x = x*10 + s[j] - '0';
                j ++;
            }
            num.push(x);
            i = j-1;
        }
        else if (s[i] == '(')
        {
            op.push(s[i]);
        }
        else if (s[i] == ')')
        {
            while (op.top() != '(')
            {
                eval();
            }
            op.pop();
        }
        else 
        {
            while (op.size() && h[op.top()] >= h[s[i]])
            {
                eval();
            }
            op.push(s[i]);
        }
    }

    while (op.size()) eval();

    cout << num.top() << endl;

    return 0;
}

非模板

思路

思路很简单，就是逐个字符读取

1. 读取到（时，表明之后肯定有），同理)时前面肯定有配对的（,所以）直接返回即可
2. 如何实现运算符优先级
   这里在更新的时候加上ah，代表前一个运算数字
   如果是低优先级，则直接运算即可
   c res += ah;
   高优先级，则表明先前的数ah要和当前的数即时运算
   res -= ah; ah *= getNum(); res += ah;
   这里ah全都用加法是因为在读取字符的时候，如果是减法，就会给ah = -1*getNum()，来保证res回退操作的一致性

Debug

1. 第一次出错在没有考虑运算符优先级，直接加减乘除相同操作顺下来，导致错误
2. 第二次在于设计问题，没有考虑到Fun中也可能读取到（，而之前的写法（只在getNum中，因此在Fun中多加了一个if，解决。

代码

#include <iostream>
#include <cstring>

using namespace std;

typedef long long ll;

string s;
ll ans;
ll ind = 0;

ll Fun();
ll getNum();

ll getNum()
{
    if (ind >= s.size())
    {
        return 0;
    }
    if (s[ind] == '(')
    {
        ind ++;
        return Fun();
    }
    else 
    {
        ll res = 0;
        while (s[ind] >= '0' && s[ind] <= '9' && ind < s.size())
        {
            res *= 10;
            res += s[ind] - '0';
            ind ++;
        }
        return res;
    }
}

ll Fun()
{
    ll res = 0;
    ll ah;

    {
        ah = getNum();
        res = ah;
    }

    while (ind < s.size())
    {
        char t = s[ind++];

        if (t == ')')
        {
            return res;
        }
        else if (t == '+')
        {
            ah = getNum();
            res += ah;
        }
        else if (t == '-')
        {
            ah = -1*getNum();
            res += ah;
        }
        else if (t == '*')
        {
            res -= ah;
            ah *= getNum();
            res += ah;
        }
        else if (t == '/')
        {
            res -= ah;
            ah /= getNum();
            res += ah;
        }
        else if (t == '(')
        {
            ah = getNum();
            res += ah;
        }
        else {
            printf ("Warning %lld %c \n", res, t);
            return 0;
        }
    }

    return res;
}

int main ()
{
    cin >> s;
    ans = Fun();
    cout << ans;
}

/*
29

(3+5*4/2+2*(1+1)*(2+2))
*/

/*
275

(3/((1)*1)-3)+2*3-1-2-1-((1-3))*2-3+1-3-3-3*2-((2*2)+1*3)*3+2-2*3+3+1+2+(3+3)/3/2*3+2-(1*2/1)+2*3+2/2+3+(((2*2)))*2+2*2/2*2-(1/3)-1+3/2-1+((3*2)/3*2)+3*3*2*2+1-2+(1+1)*1+2*2+2*3-2+(((2*2)))-2*2+2-2-3-2-(3-2+2)/3*2/2/2/3-2+(1*1)*3*3*1+((2*(1-3)))*1*3/1+3*1*2-(((2+2))/3)*2*3*1+3/(3/3*1)*1*2*2*1-3*(1-2)*3/2/1+(3*((1)*2))*3/1-1*2*2/2+((3*(2)*3)*1)+1*2*1-2+(1*(1*3))/1+1/2/3-((1/3))/2*2+2/1+3/(2*2*3)*3/3*3+2-((1/(1+1)))/3-1/3*1+3-2-((2*2))+2-3+2/1+((1/1-1)+2)/3*3-1-2+1-(3*2)/3+3-3-(2+1)*2+2*2-1-(3-((1)*2)*1)-1/3-2+3-(1*(3)+3)*3+1*3*3*2+((3*1))*1/2-1-3+((1+3*2)+1)/1/1/1+3*2-1/(1/3-1+2)+1*2+2-2*3+2*3/((2-1))+3-1/1-2/2-(3-3+3)*2*3+2-((3/(3))*1)/3*1*1+(((2-3)*2))/3-2+3+1-(3*2/3)*3*1*1*3-(3/(2*3)/2)+3/3*3-2*2-2+((2*3-3))/3-3-1+2*1*1-(3*3)/1*(2-2)*3*2-1-3*3+(2*(3*3))+3/2+1*3-(((3*3))*3)*1/1+3-(3*(3*3)/3-1)*3+3-2-1+2+(((1*2))*1)+2*3*2+2*((1+1*3)*1)-3+2*3-1*2+(3*2-(2)*2)/2*3*1-3+1+2-((1*(3)*3+3))+3+1/1/2+2*1+1+1*((3+2))/3*2-2-1*1-(3/(3+3)*3)/2-3*3-1-2-1+(1/3)+2-3*1*1-(3/(3+3))*2-3*3-3-((3*1)/2)+3+3*1/3/3-(2-1-1)/2-1*1*2+(3+1)*1+2*2*3-1+((1-3)+1)-3*1/3+((1-3))+3-1/3*2+(1-(3*2)+1)*1/1*2/1+(((2*3)))/2*2*3*2-((3/2))-(1+2*1)+2+2/3-3*1-(3*(2/1+2))-3+1-3/3+1*2-(((1/1))*2)+3*1*2+(3/(2*(2))+3)*1*1*3-2*3+(2/(1-(1-3))*1)*1*3+2/2*1-(3-1*1+2)/1/1/2*1+((3-3-1)-2)+1-3*3/1-3/3*2*(3+3)-3*2*2+1+3-3*(1/2)*1*3/1+(2/3+(2)+1)-2+2+3/3-((1-2)+1)/2-1*3+1*((2*2-2)/1)+3*3*3*3*3-((3*(3))-3)+1*1*3*2+1+(3-2/1)*2*2+3*1+1+1*((1-2))-2/2-1+3+2+(3-(2+2))-2-2/2-2*3/1+2/(1*1/3+1)-3+2-2*3-2+((1+2)*3)/2-1-3-1*1-2+2*(((2/1)))/2-3*1-1*3+(1/3-(1*3))*2*3/2*3/2-((1*3))/2-2*1/2+2/2*(3-3)+1-3*1+2+(1+(1-3))-1+2-2+1-(2-1)+1/2-2*2+2-((1-3*2)+2)/3*1*3-3-1-((3-(2*3)))*3-1*3*1*1-1+((3*(1))*3)+3*1-2+((3*2))+3+1*3*3+3+(3*1)*1*(3/1)*2*1-2*1/2+(3-(2)*3)+2-3-3-2+2-((1/1))*2*1/1*2/3+(2*3)-2+3/3+1*1-((1+(3))*2)*2+1+2*3+(3-(1+2))-2-3*2*2*2-3+(3+(1)/3)/2*3+3*3-3-(((2*2))*1)*2/1/1*1*1*1-(3/1)*1/2/1-3/3+1-1+(2-(3-1))*2+2*2*2*1-3+((3+(1))*2)*2+1-2/3*1+(2+(1)*1-3)/2*1/1+3+(2-1*3)/2+3*3+2*2+(3*2*1-3)+2+3*2-1-1*(3*2)*2-2/1-2-3*1
*/