题目链接

  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 ;
}

最新文章

  1. Mac下Intellij IDEA Console中文是?
  2. 关于window.onload,window.onbeforeload与window.onunload
  3. form 登陆跳转页面练习(未连接数据库)和连接数据库版
  4. 20145305 《Java程序设计》第8周学习总结
  5. hdu 5091(线段树+扫描线)
  6. 我理解的C++虚函数表
  7. 按需讲解之Supervisor
  8. 关于Hibemate
  9. NodeJs-- 新建项目实例
  10. C语言对齐
  11. php文件基本操作与文件管理功能
  12. 轻量级.Net Core服务注册工具CodeDi发布啦
  13. Java开发笔记(五十六)利用枚举类型实现高级常量
  14. CGI 、FastCGI、PHP-CGI、PHP-FPM 定义以及与nginx的应用关系
  15. 自学Zabbix13.2 分布式监控proxy配置
  16. 用uart实现printf函数
  17. 转载别人的一篇关于git的文章
  18. Visual Leak Detector原理剖析
  19. 关闭window端口445
  20. HDU4786_Fibonacci Tree

热门文章

  1. MySQL备份和还原数据库及慢查询日志使用
  2. 洛谷 P1330 封锁阳光大学
  3. 10048 - Audiophobia (Floyd)
  4. Asp.Net Core 进阶(三)—— IServiceCollection依赖注入容器和使用Autofac替换它
  5. mac 上node.js环境的安装与测试【转】
  6. 使用custom elements和Shadow DOM自定义标签
  7. POJ 3080 Blue Jeans、POJ 3461 Oulipo——KMP应用
  8. PAT 乙级 1012
  9. Linux-ngnix服务(二)
  10. 【php】运算符优先级界定