题解 | #序列模式匹配#

先循环遍历确定一个答案范围，然后以这个范围作为基点作滑动窗口，当这个滑动窗口长度比当前答案小，则改为当前答案。

#include <iostream>
#include <string>
#include <vector>
using namespace std;
bool have(string t,string p,int tstart,int m){
    int n=p.size();
    vector<int> dp;
    for(int i=0;i<n;i++){
        for(int j=tstart;j<m;j++){
            if(p[i]==t[j]){
                dp.push_back(j);
                //j<m-1?tstart=j+1:tstart=m-1;
                tstart=j+1;
                break;
            }
        }
    }
    if(dp.size()==n)    return true;
    else    return false;
}
int main(){
    string t,p;
    while(cin>>t>>p){
        int m=t.size();
        int n=p.size();
        vector<int> dp;
        int ans=0;
        int tstart=0;
        for(int i=0;i<n;i++){
            for(int j=tstart;j<m;j++){
                if(p[i]==t[j]){
                    dp.push_back(j);
                    //j<m-1?tstart=j+1:tstart=m-1;
                    tstart=j+1;
                    break;
                }
            }
        }
        if(dp.size()<n)  cout<<"-1 -1"<<endl;
        else if(dp.size()==n&&dp[0]==0&&dp[n-1]==n-1)  cout<<"0 "<<n-1<<endl;
        else{
            int start=dp[0],end=dp[n-1];
            ans=dp[n-1]-dp[0];
            for(int i=dp[0];i<m;i++){
                for(int j=m-1;j>=max(i,dp[n-1]);j--){
                    if(have(t,p,i,j+1)&&ans>j-i){
                        ans=j-i;
                        start=i;
                        end=j;
                    } 
                        
                }
            }
            cout<<start<<" "<<end<<endl;
        }
        
    }
    return 0;
}