题解 | #序列模式匹配#

#include <iostream>
#include <string>
#include <vector>
using namespace std;
 
int main()
{
    string text,pattern;
    while(cin >> text >> pattern) {
        int n = text.size(), m = pattern.size();
        vector<vector<int>> dp(n,vector(n,0));
        bool flag = false;
        for(int k = 0; k < n; k++) {
            for(int i = 0; i + k < n; i++) {
                if(text[i + k] == pattern[dp[i][max(i + k - 1, 0)]])
                    dp[i][i + k] = dp[i][max(i + k - 1, 0)] + 1;
                else
                    dp[i][i + k] = dp[i][max(i + k - 1, 0)];
                if(dp[i][i + k] >= m) {//确保k是最小的
                    flag = true;
                    cout << i << " " << i + k << endl;
                }
                if(flag) break;
            }
            if(flag) break;
        }
        if(!flag) cout << "-1 -1" << endl;
    }
    return 0;
}