1492C Maximum width

题面

定义一个字符串的宽度为 \(p_{i+1} - p_i\) ，现给出两个字符串，第一个字符串 \(s\) 的长度为 \(n\) ，第二个字符串 \(t\) 的长度为 \(m\) ，现在要求在第一个字符串中找出和 \(t\) 相同的字串，并求出最大的宽度

例如： \(s = abbbc\) ,\(t = abc\) ，那么有两种最大的选法： ab bb c 或者 a b bbc，即 \(\{1,2,5 \}\) 或者 \(\{1,4,5 \}\)，最大宽度为 \(3\)

思路

将字符串 \(t\) 的每个字符与字符串 \(s\) 进行比对，找到 \(t_i\) 在 \(s\) 中的位置，从左做一次并记录，记作 \(L[i]\) ，从右做一次并记录，记作 \(R[i]\)

对于每一个字符，我们都有两种选择，一种是从 \(L\) 中选择该字符的位置，另一种是从 \(R\) 中选择该字符的位置，宽度即为 \(R[i] - L[i-1]\)，遍历一次求出最大值即可

标签

贪心 思维 CF 1500

代码

#include<bits/stdc++.h>
using namespace std;

const int N = 200010;

int main(){
	int n,m;
	string s,t;
	int l[N],r[N];
	
	cin >> n >> m;
	cin >> s >> t;
	
	for(int i = 0, j = 0; i < n && j < m ; i++)
		if(s[i] == t[j])
			l[j++] = i;
	
	for(int i = n-1, j = m-1; i >= 0, j>= 0; i--)
		if(s[i] == t[j])
			r[j--] = i;
	
	int res = 0;
	for(int i = 1 ; i < m ; i++)
		res = max(res,r[i]-l[i-1]);
	cout << res << endl;
}

Codeforces 1492C Maximum width

原文：https://www.cnblogs.com/ieeeev/p/14595849.html