2018校招小米笔试-序列模式匹配

动规解法：

#include <iostream>
#include <string>
#include <memory.h>

using namespace std;

int main() {
    string text, pattern;
    cin>> text>> pattern;
    int dp[pattern.size()][text.size()];
    memset(dp, -1, sizeof(dp));
    if (pattern[0] == text[0]) dp[0][0] = 1;
    for (int j = 1; j < text.size(); ++j) {
        if (text[j] == pattern[0]) dp[0][j] = 1;
        else {
            if (dp[0][j-1] == -1) dp[0][j] = -1;
            else dp[0][j] = dp[0][j-1] + 1;
        }
    }
    for (int i = 1; i < pattern.size(); ++i) {
        for (int j = 1; j < text.size(); ++j) {
            if (pattern[i] == text[j]) {
                if (dp[i-1][j-1] != -1){
                    if (dp[i][j-1] == -1) dp[i][j] = dp[i-1][j-1] + 1;
                    else dp[i][j] = min(dp[i][j-1] + 1, dp[i-1][j-1]+1);
                }
            }else {
                if (dp[i][j-1] != -1) dp[i][j] = dp[i][j-1];
            }
        }
    }
    int length = -1;
    int index = -1;
    for (int l = 0; l < text.size(); ++l) {
        if (dp[pattern.size()-1][l] != -1) {
            if (length == -1) {
                length = dp[pattern.size()-1][l];
                index = l;
            }
            else {
                if(dp[pattern.size()-1][l] < length) {
                    length = dp[pattern.size()-1][l];
                    index = l;
                }
            }
        }
    }
    if (length == -1) cout<< -1<< " "<<-1<< endl;
    else cout<< index - length+1<< " "<<index<< endl;
    return 0;
}