aoj 0572 - Card Game is Fun

問題

問題概要

文字列bの連続した文字列が文字列aの部分文字列(連続していなくてもよい文字列)で作れる時の、最長の長さを調べる。

解法

連続文字列の先頭の文字を決め(b[i])、その文字が文字列aを先頭から見ていき、存在するかを調べ、文字存在するなら(a[k])、次に、連続文字列の先頭の次の文字(b[i + 1])を、先ほど見つけた位置の次の文字(a[k + 1])から存在するかを調べる。これを、先頭の位置を変えてすべての位置で行えばいい。 a

ミス

しっかり問題読んていなかったので、dpで最長共通部分列求めるだけかと思ってやってしまった。

コード

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


int main(void){
    int n1, n2; cin >> n1 >> n2;
    vector<int> a(n1), b(n2);
    rep(i, n1) cin >> a[i];
    rep(i, n2) cin >> b[i];

    int ans = 0;
    for (int i = 0; i < n2; ++i){//bの連続部分列topの位置に来るカードを決める
        int tmp = 0, next = 0;
        bool flag = false;
        for (int j = i; j < n2; ++j){
            for (int k = next; k < n1; ++k){//aの中で一致していくものを調べている
                if(b[j] == a[k]){
                    tmp++; next = k + 1;
                    ans = max(ans, tmp);
                    break;
                }
                if(k == n1 - 1){ flag = true; break; }
            }
            if(flag) break;
        }
    }
    printf("%d\n", ans);
    return 0;
}