TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P1767
  • 题目
  • P1767最大权值公共子串
    限制 : 时间限制 : 10000 MS   空间限制 : 65536 KB
    问题描述

    给出两个有大写和小写字母构成的字符串,每个字母对应这一个权值,请找出两个字符串中权值和最大的公共子串。
    例如:
    字母A,B,C,D对应的权值分别是10,20,30,40
    字符串1:AACCDDBB字符串2:DAACCBDDBD
    字符串1和字符串2权值和最大的公共子串是DDB,权值总和为100

    输入格式

    第一行,26个空格间隔的整数,代表大写字母'A'到'Z'对应的权值
    第二行,26个空格间隔的整数,代表小写字母'a'到'z'对应的权值
    第三行,字符串1
    第四行,字符串2
    (每个字母的权值范围[-10000,10000],字符串的长度不超过1500,要区分大小写)

    输出格式

    一个整数,表示公共子串的最大权值和

    样例输入 1

    10 20 30 40 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
    0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
    AACCDDBB
    DAACCBDDBD

    样例输出 1

    100

    样例输入 2

    10 -20 20 40 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
    0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 
    AACCDDBB
    DAACCBDDBD

    样例输出 2

    80