It Prefokery Pio - kyoupuro @ ウィキ

2035 : It Prefokery Pio

問題文

解説

与えられた文字列に含まれる最長の「回文」を出力する問題。
与えられた文字列と、それを反転させた文字列との最長共通部分列(LCS)を求めればいい。
LCSに関してはアルゴリズムイントロダクション 第15章の117～145ページに詳しい解説が載っているので参考にしてください。

プログラム

C

C++

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

int main() {
    string s1;
    while (cin >> s1) {
        string s2 = s1;
        reverse(s2.begin(), s2.end());
        string ans = "";
        int m = s1.size(), n = s2.size();
        vector< vector <int> > dp(m+1, vector<int>(n+1));
        vector< vector <int> > p(m+1, vector<int>(n+1));
 
        for (int i = 0; i < s1.size(); i++) {
            for (int j = 0; j < s2.size(); j++) {
                if (s1[i] == s2[j]) {
                    dp[i+1][j+1] = dp[i][j] + 1;
                    p[i+1][j+1] = 0;
                } else if (dp[i+1][j] < dp[i][j+1]) {
                    dp[i+1][j+1] = dp[i][j+1];
                    p[i+1][j+1] = 1;
                } else {
                    dp[i+1][j+1] = dp[i+1][j];
                    p[i+1][j+1] = -1;
                }
            }
        }
 
        for (int i = s1.size(), j = s2.size(); i > 0 && j > 0;) {
            if (p[i][j] > 0) i--;
            else if (p[i][j] < 0) j--;
            else {
                cout << s1[i-1];
                i--;
                j--;
            }
        }
        cout << endl;
    }
 
    return 0;
}

Java