【Luogu】P3856公共子串(DP)
2024-09-07 12:32:31
DP。设last[i][j]是第i个串字符'j'所在的最后的位置,f[i][j][k]是第一个串匹配到i,第二个串匹配到j,第三个串匹配到k,最多的公共子串数。
那么我们三重循环i、j、k,每次更新last数组的值。
然后在三重循环内部再加一重循环从'a'到'z',枚举公共子串的最后一个字符是什么。
然后在last里面找到这三个字符最后出现在什么位置,记为nms。
于是f[i][j][k]=f[n-1][m-1][s-1]+1。
最后输出答案即可。
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cctype>
#include<algorithm> inline long long read(){
long long num=,f=;
char ch=getchar();
while(!isdigit(ch)){
if(ch=='-') f=-;
ch=getchar();
}
while(isdigit(ch)){
num=num*+ch-'';
ch=getchar();
}
return num*f;
} long long f[][][];
char a[],b[],c[];
int x,y,z;
int last[][]; int main(){
scanf("%s%s%s",a+,b+,c+);
x=strlen(a+);y=strlen(b+);z=strlen(c+);
for(int i=;i<=x;++i){
last[][a[i]]=i; memset(last[],,sizeof(last[]));
for(int j=;j<=y;++j){
last[][b[j]]=j; memset(last[],,sizeof(last[]));
for(int k=;k<=z;++k){
last[][c[k]]=k;
for(int l='a';l<='z';++l){
int n=last[][l],m=last[][l],s=last[][l];
if(n&&m&&s) f[i][j][k]+=f[n-][m-][s-]+;
}
}
}
}
printf("%lld",f[x][y][z]);
return ;
}
最新文章
- Mac下Intellij IDEA Console中文是?
- 关于window.onload,window.onbeforeload与window.onunload
- form 登陆跳转页面练习(未连接数据库)和连接数据库版
- 20145305 《Java程序设计》第8周学习总结
- hdu 5091(线段树+扫描线)
- 我理解的C++虚函数表
- 按需讲解之Supervisor
- 关于Hibemate
- NodeJs-- 新建项目实例
- C语言对齐
- php文件基本操作与文件管理功能
- 轻量级.Net Core服务注册工具CodeDi发布啦
- Java开发笔记(五十六)利用枚举类型实现高级常量
- CGI 、FastCGI、PHP-CGI、PHP-FPM 定义以及与nginx的应用关系
- 自学Zabbix13.2 分布式监控proxy配置
- 用uart实现printf函数
- 转载别人的一篇关于git的文章
- Visual Leak Detector原理剖析
- 关闭window端口445
- HDU4786_Fibonacci Tree