hihoCoder week 60-1-String Matching Content Length 题目1 : String Matching Content Length 时间限制:10000ms 单点时限:1000ms 内存限制:256MB 描述 We define the matching contents in the strings of strA and strB as common substrings of the two strings. There are two additional restrictions on the common substrings. The first restriction here is that every common substring’s length should not be less than 3. For example: strA: abcdefghijklmn strB: ababceghjklmn The matching contents in strA and strB are substrings (“abc”, “jklmn”). Note that though “e” and “gh” are common substrings of strA and strB, they are not matching content because their lengths are less than 3. The second restriction is that the start indexes of all common substrings should be monotone increasing. For example: strA: aaabbbbccc strB: aaacccbbbb The matching contents in strA and strB are substrings (“aaa”, “bbbb”). Note that though “ccc” is common substring of strA and strB and has length not less than 3, the start indexes of (“aaa”, “bbbb”, “ccc”) in strB are (0, 6, 3), which is not monotone increasing. 输入 Two lines. The first line is strA and the second line is strB. Both strA and strB are of length less than 2100. 输出 The maximum length of matching contents (the sum of the lengths of the common substrings). 样例输入 abcdefghijklmn ababceghjklmn 样例输出 8
本题在普通的最长公共子序列问题上添加了一个限制条件，构成最长公共子序列的每一个子串长度必须大于等于3。题目中下面这段的含义就是指求的是最长公共子序列，LCS就是从左往右依次扫描找相同的字母，ccc是公共子序列，但不是最长的，因为aaabbbb更长。
The matching contents in strA and strB are substrings (“aaa”, “bbbb”). Note that though “ccc” is common substring of strA and strB and has length not less than 3, the start indexes of (“aaa”, “bbbb”, “ccc”) in strB are (0, 6, 3), which is not monotone increasing.至于题解，讨论里写得很清楚了，不过要让我自己想还真想不出来。代码实现也很简单，如下： [cpp] #include<iostream> #include<cstdio> #include<string> #include<algorithm> #include<cstdlib> using namespace std; const int kMaxLen = 2105; string a, b; int dp[kMaxLen][kMaxLen][2]; int f[kMaxLen][kMaxLen]; void Init() { for (int i = 1; i < a.size(); i++) { for (int j = 1; j < b.size(); j++) { if (a[i] == b[j]) f[i][j] = f[i – 1][j – 1] + 1; else f[i][j] = 0; } } } void Lcs() { for (int i = 1; i < a.size(); i++) { for (int j = 1; j < b.size(); j++) { dp[i][j][1] = 0; if (f[i][j] >= 3) { dp[i][j][1] = max(dp[i][j][1], dp[i – 3][j – 3][0] + 3); if (f[i][j]>3) dp[i][j][1] = max(dp[i][j][1], dp[i – 1][j – 1][1] + 1); } dp[i][j][0] = max(dp[i – 1][j][0], max(dp[i][j – 1][0], dp[i][j][1])); } } } int main() { cin >> a >> b; a = " " + a; b = " " + b; Init(); Lcs(); printf("%d\n", dp[a.size() – 1][b.size() – 1][0]); return 0; } [/cpp] 本代码提交AC，用时319MS，内存50MB。]]>