TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  训练指南  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P6065
  • 题目
  • P6065b
    限制 : 时间限制 : - MS   空间限制 : - KB
    评测说明 : 1s,512m
    问题描述

    给出两个字符串 s,t ,和一个整数 k ,进行如下操作 :
    由 1 至 length(s) 依次从 s 中选出 k 个不相交的连续的非空子串 p1,...,pk .
    由 1 至 length(t) 依次从 t 中选出 k 个不相交的连续的非空子串 q1,...,qk .
    保持 p1,...,pk 在 s 中的相对位置顺序,保持 q1,...,qk 在 t 中的相对位置顺序。
    使得 p1 = q1,p2 = q2,...,pk = qk ,且最大化选出的 k 个子串的长度之和。
    其中字符串从 1 开始标号,length(s) 表示字符串 s 的长度。

    输入格式

    第一行三个整数 n,m,k ,分别代表字符串 s,t 的长度,选出的子串的个数。
    第二行一个字符串 s .
    第三行一个字符串 t .

    输出格式

    一行一个整数,表示选出的子串长度之和的最大值。

    样例输入

    15 9 4
    ababaaabbaaaabb
    bbaababbb

    样例输出

    8

    提示

    n,m ≤ 1000,k ≤ 10 .