5982번: Forgotten Password

https://www.acmicpc.net/problem/5982

dp[i]: 0..i번째 글자를 정했을 때, 사전 순으로 가장 빠른 단어


아래 소스의 시간복잡도는 $O(l^2+l*nw*L_w)$ // $L_w$은 사전 내 단어의 최대 길이

#include<iostream>
#include<string>
using namespace std;
string w[1000], r[1001], p;
int l, nw;
int main() {
    cin >> l >> nw >> p;
    for (int i = 0; i < nw; i++) cin >> w[i];
    for (int i = 0; i < l; i++) if (!i || r[i] != "") {
        for (int j = 0; j < nw; j++) if (i + w[j].length() <= l) {
            int k = 0;
            for (; k < w[j].length(); k++) if (p[i + k] ^ '?' && p[i + k] ^ w[j][k]) break;
            if (k == w[j].length() && (r[i + k] == "" || r[i + k] > r[i] + w[j])) r[i + k] = r[i] + w[j];
        }
    }
    cout << r[l];
    return 0;
}