Codeforces Round #704 (Div. 2)-C. Maximum width

傳送門
Time Limit: 2 seconds
Memory Limit: 512 megabytes

Problem Description

Your classmate, whom you do not like because he is boring, but whom you respect for his intellect, has two strings: s s s of length n n n and t t t of length m m m.

A sequence p 1 , p 2 , … , p m p_1, p_2, \ldots, p_m p1?,p2?,…,pm?, where 1 ≤ p 1 < p 2 < … < p m ≤ n 1 \leq p_1 < p_2 < \ldots < p_m \leq n 1≤p1?<p2?<…<pm?≤n, is called beautiful, if s p i = t i s_{p_i} = t_i spi??=ti? for all i i i from 1 1 1 to m m m. The width of a sequence is defined as max ? 1 ≤ i < m ( p i + 1 ? p i ) \max\limits_{1 \le i < m} \left(p_{i + 1} - p_i\right) 1≤i<mmax?(pi+1??pi?).

Please help your classmate to identify the beautiful sequence with the maximum width. Your classmate promised you that for the given strings s s s and t t t there is at least one beautiful sequence.

Input

The first input line contains two integers n n n and m m m ( 2 ≤ m ≤ n ≤ 2 ? 1 0 5 2 \leq m \leq n \leq 2 \cdot 10^5 2≤m≤n≤2?105) — the lengths of the strings s s s and t t t.

The following line contains a single string s s s of length n n n, consisting of lowercase letters of the Latin alphabet.

The last line contains a single string t t t of length m m m, consisting of lowercase letters of the Latin alphabet.

It is guaranteed that there is at least one beautiful sequence for the given strings.

Output

Output one integer — the maximum width of a beautiful sequence.

Sample Input

5 3
abbbc
abc

Sample Onput

3

Note

In the first example there are two beautiful sequences of width 3 3 3: they are { 1 , 2 , 5 } \{1, 2, 5\} {1,2,5} and { 1 , 4 , 5 } \{1, 4, 5\} {1,4,5}.

In the second example the beautiful sequence with the maximum width is { 1 , 5 } \{1, 5\} {1,5}.

In the third example there is exactly one beautiful sequence — it is { 1 , 2 , 3 , 4 , 5 } \{1, 2, 3, 4, 5\} {1,2,3,4,5}.

In the fourth example there is exactly one beautiful sequence — it is { 1 , 2 } \{1, 2\} {1,2}.

題目大意

兩個字串s和t長度分別是n和m，
在s從左到右選一些字母組成t，
問s中所有選中的字符中，最大間距是多少，

題目保證能從s中選出t，

題目分析

要使間距最大，就要t中的某兩個相鄰的字母在s中選擇時，第一個字母盡可能往前，第二個字母盡可能往后，這樣才能使間距最大，

如s(abbbc)中選擇t(abc)，看t中相鄰兩個字母，先看a和b，a要選的盡可能靠前（其實就一種選擇），所以選第1個，b要選的盡可能靠后（可以選第2~4個），所以選第4個，這樣的話它的最大間距就是4-3=3，同理看b和c時，應分別選擇第2個和第5個，間距同樣是5-2=3，所以最大間距是3，

解題思路

先從前往后遍歷一遍，得到t中每個字母最靠前能選到s的第幾個；
再從后往前遍歷一遍，得到t中每個字母最靠后能選到s的第幾個，
考慮所有t中相鄰的兩個字母，看看第一個字母最靠前，第二個字母最靠后，間距是多少，
更新最大間距，直到遍歷完t，

AC代碼

#include <bits/stdc++.h>
using namespace std;
#define mem(a) memset(a, 0, sizeof(a))
#define dbg(x) cout << #x << " = " << x << endl
#define fi(i, l, r) for (int i = l; i < r; i++)
#define cd(a) scanf("%d", &a)
typedef long long ll;
char s[200010];
char t[200010];
int zuiQian[200010]; //最靠前能選到s中的第幾個
int zuiHou[200010]; //最靠后能選到s中的第幾個
int main()
{
    int n, m, M = 1;
    scanf("%d%d", &n, &m);
    scanf("%s", s);
    scanf("%s", t);
    int lastT = -1;
    for (int i = 0; i < m; i++)
    {
        while (s[++lastT] != t[i]) //找到s中第一個沒有選過的并且與t的下一個相同的字母，
            ;
        zuiQian[i] = lastT;
    }
    lastT = n;
    for (int i = m - 1; i >= 0; i--)
    {
        while (s[--lastT] != t[i])
            ;
        zuiHou[i] = lastT;
    }
    for (int i = 1; i < m; i++)
    {
        M = max(M, zuiHou[i] - zuiQian[i - 1]); //更新最大值
    }
    printf("%d\n", M);
    return 0;
}

注意事項

while (s[++lastT] != t[i]);是打比賽時確定s中下一個位置的簡便寫法，

學會的話打比賽會快億點點，但是小心不要用錯了哦，