TouchStone
  Please Login
Login Sign Up
距离明年CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 Homepage  Problem Set  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P6065
  • Problem
  • P6065b
    Limits : Time Limit : - MS   Memory Limit : - KB
    Judgment Tips : 1s,512m
    Description

    给出两个字符串 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 的长度。

    Input Format

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

    Output Format

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

    Sample Input

    15 9 4
    ababaaabbaaaabb
    bbaababbb

    Sample Output

    8

    Hint

    n,m ≤ 1000,k ≤ 10 .