Codeforces Remove the Substring(hard version)

https://codeforces.com/problemset/problem/1203/D2

영어 지문은 아직도 읽기 까다로운 것 같습니다. substring이 연속할 필요가 없다는 조건을 연속해야 한다는 조건으로 보고 한참 헤맸습니다.

짚더미(긴 문자열)을 s, 바늘(찾는 문자열)을 t라고 하겠습니다.

t에 있는 모든 문자들이 s에서 왼쪽에서 몇번째로 나오는지, 오른쪽에서 몇번째로 나오는지만 저장한다면 이 문제는 간단하게 풀 수 있습니다.

좌측에 있는 문자열, 중간에 있는 문자열, 우측에 있는 문자열을 뺄 수 있습니다. 좌측에 있는 문자열과 중간에 있는 문자열은 가장 마지막에 찾은 index를 이용하면 쉽게 구할 수 있으므로 pass 하겠습니다.

중간에 있는 문자열도 마찬가지로 쉽게 구할 수 있습니다. 왼쪽에서부터 x번째의 문자가 갖는 index와 오른쪽에서부터 tl-x(tl은 t의 길이)의 문자가 갖는 index 사이에 있는 문자열이 최대로 뺄 수 있는 문자열이기 때문입니다.

따라서 복잡도는 O(n)이 됩니다.

#include<bits/stdc++.h>
using namespace std;
const int SZ=200005;
int ll[SZ];
int rr[SZ];
int main(void){
	ios::sync_with_stdio(false); cin.tie(NULL);
	string s; cin>>s;
	string t; cin>>t;
	int sl=(int)s.size();
	int tl=(int)t.size();
	int p=0;
	for(int i=0;i<tl;i++){
		while(t[i]!=s[p]){
			p++;
		}
		ll[i]=p++;
	}
	p=0;
	for(int i=0;i<tl;i++){
		while(t[tl-i-1]!=s[sl-p-1]){
			p++;
		}
		rr[i]=sl-1-(p++);
	}
	int ans=max(sl-1-ll[tl-1],rr[tl-1]);
	for(int i=0;i<tl;i++){
		ans=max(ans,rr[tl-2-i]-ll[i]-1);
	}
	cout<<ans;
	return 0;
}

codeforces Remove the Substring(hard version)