USACO 2.3 Longest Prefix

题目描述

The structure of some biological objects is represented by the sequence of their constituents, where each part is denoted by an uppercase letter. Biologists are interested in decomposing a long sequence into shorter sequences called primitives.

We say that a sequence S can be composed from a given set of primitives P if there is a some sequence of (possibly repeated) primitives from the set whose concatenation equals S. Not necessarily all primitives need be present. For instance the sequence ABABACABAABcan be composed from the set of primitives

   {A, AB, BA, CA, BBC}

The first K characters of S are the prefix of S with length K. Write a program which accepts as input a set of primitives and a sequence of constituents and then computes the length of the longest prefix that can be composed from primitives

PROGRAM NAME: prefix

Solution

考虑dp,显然如果当前的字符串从后往前截了有一段集合中的串且截去这段串后的字串是合法的,那么当前串也是合法的,因此设\(dp[i]\)为长度为i的串的合法性。

我们可以把所有长度相同的串丢到一个set里面,每次查找的时候从与当前串长度相等的串中寻找即可

Code

/*
PROB: prefix
LANG: C++
ID: yizhuor1
*/
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair

using namespace std;

typedef long long LL;
typedef pair<int, int> pii;

template <typename T> inline int Chkmax (T &a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> inline int Chkmin (T &a, T b) { return a > b ? a = b, 1 : 0; }

template <typename T> inline T read(){
    T sum = 0;
    int fl = 1,ch = getchar();
    for(; !isdigit(ch); ch = getchar()) if(ch == '-') fl = -1;
    for(; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + ch - '0';
    return sum * fl;
}

const int maxn = 2e5 + 5;

int size;
int dp[maxn];
string st;
set<string> s[20];

inline void Solve (){
    int ans = 0;
    dp[0] = 1;
    string tmp;
    tmp = " ";
    while(cin >> st){
        tmp = tmp + st;//把所有串合并成一个
    }
    for(int i = 1; i < tmp.size(); i++){//枚举子串
        for(int j = min(i,size); j >= 1; j--){
            string sub = tmp.substr(i - j + 1,j);
            if(s[sub.size()].count(sub) == 1 && dp[i - j] == 1){
                ans = i;
                dp[i] = 1;//更新当前状态
                break;
            }
        }
    }
    printf("%d\n",ans);
}

inline void Input (){
    while(cin >> st){
        if(st == ".") break;
        s[st.size()].insert(st);//把所有长度相同的串丢到一个set里面
        Chkmax(size,(int)(st.size()));
    }
}

int main(){
//  freopen("prefix.in","r",stdin);
//  freopen("prefix.out","w",stdout);
    Input();
    Solve();
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注