题解 P1470 【最长前缀 Longest Prefix】

momo5440 · 2018-12-30 15:30:36 · 题解

正如前辈们所说的，这是道dp题，dp的是状态，如果当前的字符串从后往前截了有一段集合中的串且截去这段串后的字串是合法的话那么当前串也是合法的，之前的大佬已说过了，所以我再次介绍一种优化方法（经过我的老师提醒），那就是用STL中的set(集合感觉题目中已经提示了），我们没有必要把子串与所有集合里的串作比较，只有比较跟他长度相等的就行了,set里面是一棵平衡树只需logn的时间就可以找到要求的东西 说了这么多，上代码，代码里也有注释。

#include <iostream>
#include <set>
#include <cstring>
using namespace std;
int dp[200005],m;
set<string> s[20];
int main(){
    string tp;
    while (cin>>tp){
        if (tp==".") break;
        s[tp.size()].insert(tp);//存到他大小的集合中 
        m=max(m,int(tp.size()));
    }
    int i,ans=0;
    dp[0]=1;//初始化 
    string n;
    n=" ";
    while (cin>>tp){
        n=n+tp;//将所有的串合成一个 
    }
    for (i=1;i<n.size();i++){//枚举子串 
        for (int j=min(i,m);j>=1;j--){
            string tt=n.substr(i-j+1,j);//截除子串 
            if (s[tt.size()].count(tt)==1&&dp[i-j]==1){//如果合法 
                ans=i;//必定是最大的 
                dp[i]=1;//本身也合法 
                break;//没必要搜下去了 
            }
        }
    }
    cout<<ans;
}