verifying_test/AOJ/1227/trace.test.cpp

• View this file on GitHub
• Last update: 2025-10-19 18:34:23+09:00
• Problem: https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1227

Depends on

• Trace（経路復元） (marathon/trace.cpp)

Code

#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1227"

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

#define call_from_test
#include "../../../marathon/trace.cpp"
#undef call_from_test

string char_to_digit = "22233344455566677778889999";

int solve_testcases() {
    int N; cin >> N;
    if (N == 0) return 1;
    vector<string> words(N);
    for(auto &e : words) cin >> e;
    string seq; cin >> seq;

    vector<string> word_digits(N);
    for(int i=0; i<N; i++) {
        string digits = "";
        for(char c : words[i]) {
            digits += char_to_digit[c - 'a'];
        }
        word_digits[i] = digits;
    }
    
    Trace<string> trace;
    vector<int> terminals;
    auto go = [&](auto &&self, int pos, int id) -> void {
        if (pos == seq.size()) {
            terminals.emplace_back(id);
            return;
        }
        for(int i=0; i<N; i++) {
            if (pos + word_digits[i].size() > seq.size()) continue;
            if (seq.substr(pos, word_digits[i].size()) == word_digits[i]) {
                int nxt = pos + word_digits[i].size();
                self(self, nxt, trace.add(words[i], id));
            }
        }
    };
    go(go, 0, -1);
    vector<string> answers;
    for(int id : terminals) {
        vector<string> words = trace.get(id);
        string answer = "";
        for(int i=0; i<(int)words.size(); i++) {
            answer += words[i];
            if (i + 1 < (int)words.size()) answer += " ";
            else answer += ".";
        }
        answers.emplace_back(answer);
    }
    sort(answers.begin(), answers.end());
    for(auto answer : answers) {
        cout << answer << endl;
    }
    cout << "--" << endl;
    return 0;
}

int main() {
    while(!solve_testcases());
    return 0;
}

#line 1 "verifying_test/AOJ/1227/trace.test.cpp"
#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1227"

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

#define call_from_test
#line 1 "marathon/trace.cpp"
template <typename Tp>
class Trace {
public:
    Trace() = default;

    int add(const Tp& value, int parent) {
        log_.emplace_back(value, parent);
        return (int)log_.size() - 1;
    }

    vector<Tp> get(int index) const {
        vector<Tp> result;
        while (index >= 0) {
            result.emplace_back(log_[index].first);
            index = log_[index].second;
        }
        reverse(result.begin(), result.end());
        return result;
    }

private:
    vector<pair<Tp, int>> log_;
};
#line 10 "verifying_test/AOJ/1227/trace.test.cpp"
#undef call_from_test

string char_to_digit = "22233344455566677778889999";

int solve_testcases() {
    int N; cin >> N;
    if (N == 0) return 1;
    vector<string> words(N);
    for(auto &e : words) cin >> e;
    string seq; cin >> seq;

    vector<string> word_digits(N);
    for(int i=0; i<N; i++) {
        string digits = "";
        for(char c : words[i]) {
            digits += char_to_digit[c - 'a'];
        }
        word_digits[i] = digits;
    }
    
    Trace<string> trace;
    vector<int> terminals;
    auto go = [&](auto &&self, int pos, int id) -> void {
        if (pos == seq.size()) {
            terminals.emplace_back(id);
            return;
        }
        for(int i=0; i<N; i++) {
            if (pos + word_digits[i].size() > seq.size()) continue;
            if (seq.substr(pos, word_digits[i].size()) == word_digits[i]) {
                int nxt = pos + word_digits[i].size();
                self(self, nxt, trace.add(words[i], id));
            }
        }
    };
    go(go, 0, -1);
    vector<string> answers;
    for(int id : terminals) {
        vector<string> words = trace.get(id);
        string answer = "";
        for(int i=0; i<(int)words.size(); i++) {
            answer += words[i];
            if (i + 1 < (int)words.size()) answer += " ";
            else answer += ".";
        }
        answers.emplace_back(answer);
    }
    sort(answers.begin(), answers.end());
    for(auto answer : answers) {
        cout << answer << endl;
    }
    cout << "--" << endl;
    return 0;
}

int main() {
    while(!solve_testcases());
    return 0;
}

Back to top page