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

### 目录

• Codeforces Round #704 (Div. 2)-C. Maximum width
• Problem Description
• Input
• Output
• Sample Input
• Sample Onput
• Note
• 题目大意
• 题目分析
• 解题思路
• AC代码
• 注意事项

## 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 of length n n and t t of length m m .

A sequence p 1 , p 2 , … , p m p_1, p_2, \ldots, p_m , where 1 ≤ p 1 < p 2 < … < p m ≤ n 1 \leq p_1 < p_2 < \ldots < p_m \leq n , is called beautiful, if s p i = t i s_{p_i} = t_i for all i i from 1 1 to 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) .

### Input

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

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

The last line contains a single string t t of length 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 : they are { 1 , 2 , 5 } \{1, 2, 5\} and { 1 , 4 , 5 } \{1, 4, 5\} .

In the second example the beautiful sequence with the maximum width is { 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\} .

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

# AC代码

#include
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中下一个位置的简便写法。