- #include
- using namespace std;
- typedef long long ll;
- const int N=5e5+10;
- const long long inf = 0x7f7f7f7f7f7f7f7f;
- #define endl '\n'
- typedef pair<int,int>pii;
- int dp[N][3];
- struct node{//字典树
- int dex=0;
- int d[N][30];
- int cnt[N];
- void insert(string s){
- int x=0;
- for(int i=0;i
size();i++){ - if(d[x][s[i]-'a']){//当前结点有的话就按照当前结点顺序走
- x=d[x][s[i]-'a'];
- continue;
- }
- d[x][s[i]-'a']=++dex;//分配新的结点
- x=d[x][s[i]-'a'];
- }
- cnt[x]++;
- }
- }A,B;
- int main(){
- int n,m;
- cin>>n;
- string a,b;
- for(int i=1;i<=n;i++){
- cin>>a;
- A.insert(a);
- }
- cin>>m;
- for(int i=1;i<=m;i++){
- cin>>b;
- B.insert(b);
- }
- string c;
- cin>>c;
- c=' '+c;
- // for(int i=0;i<=c.size();i++)dp[i][0]=dp[i][1]=inf;
- memset(dp,0x3f,sizeof(dp));
- dp[0][1]=0;
- dp[0][0]=0;
- for(int i=1;i<=c.size();i++){
- int x=0;
- for(int j=i;j<=c.size();j++){
- if(A.d[x][c[j]-'a']){
- x=A.d[x][c[j]-'a'];
- }
- else break;
- if(A.cnt[x])dp[j][0]=min(dp[j][0],dp[i-1][1]+1);//由结果倒推
- }
- x=0;
- for(int j=i;j<=c.size();j++){
- if(B.d[x][c[j]-'a']){
- x=B.d[x][c[j]-'a'];
- }
- else break;
- if(B.cnt[x])dp[j][1]=min(dp[j][1],dp[i-1][0]+1);
- }
- }
- ll op=min(dp[c.size()-1][0],dp[c.size()-1][1]);
- if(op>=1e9)cout<<"-1"<
- else cout<
- }
-
相关阅读:
数据库实验一 数据表的创建与修改管理
使用jQuery获取不同元素的ID
一站式元数据治理平台——Datahub
信息系统项目管理师核心考点(五十五)配置管理员(CMO)的工作
表单校验,日期比较
2022最新SpringCloud面试题附完整答案
开快递驿站能赚钱么?去掉成本,一个月能赚多少钱?
Python如何使用Redis
笔记01:第一行Python
如何发布离线地图服务及二次开发API
-
原文地址:https://blog.csdn.net/m0_61094896/article/details/133171425