洛谷 P1470 最长前缀 Longest Prefix

题目传送门

解题思路:

其实思路没那么难,就是题面不好理解,解释一下题面吧.

就是在下面的字符串中找一个子串,使其以某种方式被分解后,每部分都是上面所给集合中的元素.

AC代码:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<set>

using namespace std;

set<string> a[11];
string l,k,p;
bool f[200003];
int ans = -1,m;

inline int max(int s,int d) {
    if(s >= d) return s;
    return d;
}

int main() {
    while(true) {
        cin >> l;
        if(l == ".") break;
        a[l.length()].insert(l);
        m = max(m,l.length());
    }
    while(cin >> p) {
        k = k + p;
    }
    f[-1] = 1;
    for(int i = 0;i < k.length(); i++) {
        for(int j = min(i,m-1);j >= 0; j--) {
            string o = k.substr(i - j,j + 1);//提取从i-j开始,长度为5的k的子串 
            if(a[o.length()].count(o) && f[i-j-1]) {//如果o可以被构成,并且除了o其它的也能被构成 
                ans = i;
                f[i] = 1;
                break;
            }
        }
    }
    printf("%d",ans + 1);
    return 0;
}