USACO Section 2.3 The Longest Prefix

なかなか難しい問題だと思っていたが、今日見てみると、こんな水だった.
dp[i]で前のi文字がセット内の要素で表すことができるかどうかを表す
初期dp[0]=1
そして各位置iに対して、すべての辞書の中の要素を列挙し、その要素の長さをjとすると、i-jからiまでの文字列をその要素と比較し、一致してdp[i-j]が1であれば、dp[i]を更新するが、複雑度が高いようだ
2000*200000は、通れないと思っていたが、結局通り過ぎてしまった.ネット上の多くの人もこのような3重サイクルで通り過ぎた. 

/*
ID: sdj22251
PROG: prefix
LANG: C++
*/
#include <iostream>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cmath>
#include <ctime>
#define MAXN 305
#define INF 100000000
#define eps 1e-7
#define PI 3.1415926535898
using namespace std;
char dic[205][11];
string s;
char tmp[105];
int dp[200005];
int main()
{
    freopen("prefix.in","r",stdin);
    freopen("prefix.out","w",stdout);
    int cnt = 0;
    while(scanf("%s", dic[cnt]) != EOF)
    {
        if(strcmp(dic[cnt], ".") == 0) break;
        cnt++;
    }
    s = "";
    while(gets(tmp) != 0)
        s += tmp;
    int len = s.length();
    dp[0] = 1;
    int mx = 0;
    for(int i = 1; i <= len; i++)
    {
        for(int j = 0; j < cnt; j++)
        {
            int ll = strlen(dic[j]);
            if(ll > i) continue;
            bool flag = true;
            for(int k = ll - 1; k >= 0; k--)
                if(s[i - k - 1] != dic[j][ll - 1 - k])
                    flag = false;
            if(flag && dp[i - ll])
                dp[i] = 1;
        }
        if(dp[i]) mx = max(mx, i);
    }
    printf("%d
", mx);
    return 0;
}