【Leetcode】3008. Find Beautiful Indices in the Given Array II

题目地址：

https://leetcode.com/problems/find-beautiful-indices-in-the-given-array-ii/description/

给定三个字符串s ss，a aa和b bb，还有一个正整数k kk，求所有的i ii满足s [ i : ] s[i:]s[i:]以a aa为前缀，并且s ss含有子串b bb，且b bb开始的位置（之一）和i ii的距离小于等于k kk。返回所有满足条件的i ii。

先用KMP求出a aa和b bb在s ss中出现的所有位置的下标，这样得出两个下标数组v a v_ava​和v b v_bvb​，并且它们都是单调增的。遍历v a v_ava​，对于每个i ii，求出j jj使得j jj是满足v b [ j ] ≥ i − k v_b[j]\ge i-kvb​[j]≥i−k的最小的数，然后判断v b [ j ] ≤ i + k v_b[j]\le i+kvb​[j]≤i+k是否成立。如果成立，则将i ii加入答案。注意j jj是不需要回退的。代码如下：

classSolution{public:vector<int>beautifulIndices(string s,string a,string b,intk){s=" "+s;a=" "+a;b=" "+b;autof=[](auto&s,auto&p){intm=p.size()-1,n=s.size()-1;vector<int>ne(m+1);for(inti=2,j=0;i<=m;i++){while(j&&p[i]!=p[j+1])j=ne[j];if(p[i]==p[j+1])j++;ne[i]=j;}vector<int>res;for(inti=1,j=0;i<=n;i++){while(j&&s[i]!=p[j+1])j=ne[j];if(s[i]==p[j+1])j++;if(j==m){res.push_back(i-j);j=ne[j];}}returnres;};autova=f(s,a),vb=f(s,b);intj=0;vector<int>res;for(inti:va){intl=i-k,r=i+k;while(j<vb.size()&&vb[j]<l)j++;if(j<vb.size()&&vb[j]<=r)res.push_back(i);}returnres;}};

时空复杂度O ( l s + l a + l b ) O(l_s+l_a+l_b)O(ls​+la​+lb​)。