https://www.acwing.com/activity/content/introduction/57/group_buy/133857/

#include <iostream>
using namespace std;
const int N = 1e5 + 10, M = 1e6 + 10;
char p[N], s[M];
int ne[N];
int main()
{
    int n, m;
    cin >> n >> p + 1 >> m >> s + 1;
    for (int i = 2, j = 0; i <= n; i++)
    {
        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 <= m; i++)
    {
        while (j && s[i] != p[j + 1]) j = ne[j];
        if (s[i] == p[j + 1]) j++;
        if (j == n)
        {
            printf("%d ", i - n);
            j = ne[j];
        }
    }
}

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
int n, m;
int s[N];
vector<int> adj[N];
int find_root(int x)
{
    if (s[x] != x) return s[x] = find_root(s[x]);
    return s[x];
}
void merge(int x1, int x2)
{
    int root1 = find_root(x1), root2 = find_root(x2);
    s[root1] = root2;
}
bool check()
{
    for (int i = 1; i <= n; i++) s[i] = i;
    for (int u = 1; u <= n; u++)
    {
        for (int j = 1; j < adj[u].size(); j++)
        {
            int v = adj[u][j];
            merge(adj[u][0], v);
            if (find_root(v) == find_root(u)) return false;
        }
    }
    return true;
}
int main()
{
    cin >> n >> m;
    for (int i = 0; i < m; i++)
    {
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b), adj[b].push_back(a);
    }
    if (check()) puts("Yes");
    else puts("No");
}

#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int n, a[N], q;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> q;
    for (int i = 0; i < n; i++) cin>> a[i];
    while (q--)
    {
        int l = 0, r = n, c;
        cin >> c;
        while (l < r)
        {
            int mid = l + r >> 1;
            if (a[mid] < c) l = mid + 1;
            else r = mid;
        }
        if (a[l] != c)
        {
            cout << -1 << ' ' << -1 << endl;
            continue;
        }
        cout << l << ' ';
        r = n - 1;
        while (l < r)
        {
            int mid = l + r + 1 >> 1;
            if (a[mid] <= c) l = mid;
            else r = mid - 1;
        }
        cout << l << endl;
    }
}

#include <iostream>
#include <unordered_set>
#include <algorithm>
using namespace std;
const int N = 110;
int n;
string s;
bool check(int val)
{
    unordered_set<string> st;
    for (int i = 0; i + val <= s.size(); i++)
    {
        string sub_str = s.substr(i, val);
        if (st.count(sub_str)) return false;
        st.insert(sub_str);
    }
    return true;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    cin >> s;
    int l = 1, r = n;
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    cout << l << endl;
}

#include <iostream>
using namespace std;
const int N = 1010;
int s[N][N], d[N][N], n, m, q;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m >> q;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) 
            cin >> s[i][j];
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            d[i][j] = s[i][j] - s[i - 1][j] - s[i][j - 1] + s[i - 1][j - 1];
    while (q--)
    {
        int x1, y1, x2, y2, c;
        cin >> x1 >> y1 >> x2 >> y2 >> c;
        d[x1][y1] += c, d[x1][y2 + 1] -= c, d[x2 + 1][y1] -= c, d[x2 + 1][y2 + 1] += c;
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            d[i][j] += d[i - 1][j] + d[i][j - 1] - d[i - 1][j - 1];
            cout << d[i][j] <<' ';
        }
        cout << endl;
    }
}

#include <iostream>
using namespace std;
const int N = 1e5 + 10;
int n, m, d[N], s[N];
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> s[i], d[i] = s[i] - s[i - 1];
    while (m--)
    {
        int l, r, c;
        cin >> l >> r >> c;
        d[l] += c, d[r + 1] -= c;
    }
    for (int i = 1; i <= n; i++) d[i] += d[i - 1], cout << d[i] << ' ';
}

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5 + 10;
int n, a[N], d[N];
int main()
{
    cin >> n;

    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) d[i] = a[i] - a[i - 1];
    long long pos = 0, neg = 0;    
    for (int i = 2; i <= n; i++)
    {
        if (d[i] > 0) pos += d[i];
        else neg += -d[i];
    }
    cout << max(neg, pos) << endl << abs(neg - pos) + 1 << endl;
}

//最后一步是删除f[i - 1][j] + 1，最后一步是插入f[i][j - 1] + 1，最后一步是替换f[i - 1][j - 1] + 0/1
#include <iostream>
using namespace std;
const int N = 1010;
int n, m, dp[N][N];
int main()
{
    char a[N], b[N];
    cin >> n >> a + 1 >> m >> b + 1;
    for (int i = 1; i <= n; i++) dp[i][0] = i;
    for (int i = 1; i <= m; i++) dp[0][i] = i;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + 1;
            dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + (a[i] != b[j]));
        }
    cout << dp[n][m];
}