SRM 698 div2 medium RepeatStringEasy

問題

問題概要

与えられた文字列から、部分文字列として、共通のもの(T)を取り出し、S = T + TのSの長さを求める問題。

解法

まず、与えられた文字列を2つに分ける。その後、その2つの文字列の最長共通部分列(LCS)の長さを求めて、2倍したものが答えの候補となる。LCSはdpで求めればいい。この操作を与えられた文字列を2つに分けるすべての場合に対して行い、その最大値を求めればいい。

ミス

すんなり行けた。 今回は2完。

コード

#include <iostream>
#include <string>
#include <cstdio>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)

class RepeatStringEasy {
public:
    int ans = 0;

    int maximalLength(string s){

        if(s.size() == 1){
            return 0;
        }
        for (int i = 0; i < (int)s.size() - 1; ++i){
            string s1 = s.substr(0, i + 1);
            string s2 = s.substr(i + 1, s.size() - i - 1);
            ans = max(ans, lcs(s1, s2));
        }
        return ans;
    }

    int lcs(string x, string y){
        int c[60][60];
        rep(i, 60)rep(j, 60) c[i][j] = 0;

        int m = x.size();
        int n = y.size();
        int maxl = 0;
        x = ' ' + x;
        y = ' ' + y;
        for (int i = 1; i <= m; ++i){
            c[i][0] = 0;
        }
        for (int i = 1; i <= n; ++i){
            c[0][i] = 0;
        }

        for (int i = 1; i <= m; ++i){
            for (int j = 1; j <= n; ++j){
                if(x[i] == y[j]){
                    c[i][j] = c[i - 1][j - 1] + 1;
                }else{
                    c[i][j] = max(c[i - 1][j], c[i][j - 1]);
                }
                maxl = max(maxl, c[i][j]);
            }
        }
        return maxl * 2;
    }
};