| 题目名称 | 3237. 最长公共子串 |
|---|---|
| 输入输出 | lcsubstr.in/out |
| 难度等级 | ★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 10 |
| 题目来源 |
 Benjamin
于2019-09-12加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：25， 提交：57， 通过率：43.86% | ||||
 wow草原 |
100 | 0.002 s | 0.59 MiB | C++ |
|
wow草原 |
100 | 0.006 s | 1.18 MiB | C++ |
|
wow草原 |
100 | 0.012 s | 3.10 MiB | C++ |
|
syzhaoss |
100 | 0.383 s | 40.06 MiB | C++ |
|
dew52 |
100 | 0.433 s | 40.52 MiB | C++ |
|
dew52 |
100 | 0.469 s | 50.65 MiB | C++ |
|
dew52 |
100 | 0.499 s | 40.52 MiB | C++ |
|
dew52 |
100 | 0.519 s | 40.52 MiB | C++ |
|
dew52 |
100 | 0.519 s | 40.52 MiB | C++ |
 瑆の時間~無盡輪迴·林蔭 |
100 | 0.557 s | 109.08 MiB | C++ |
| 关于 最长公共子串 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
后缀数组o（n+m）复杂度恐怖如斯
| ||||
|
说句实话，第一道不看题解也没有写过类似题目自己手推的DP（可能更像是递推）
前两WA都是当作了LIS来写 | ||||
【题目描述】
求两字符串的最长公共子串，例如：字符串S1为：abcdef，字符串S2为：cdefabc，其中cdef为S1和S2的最长公共子串，长度为4。
【输入格式】
2行，每行一个字符串，字符串中只包含小写字母。
【输出格式】
一个整数，表示输入的两个字符串最长公共子串的长度。
【样例输入1】
abcd efghij
【样例输出1】
0
【样例输入2】
uvwxyz z
【样例输出2】
1
【样例输入3】
abc xyzabc
【样例输出3】
3
【数据规模】
50%的数据，字符串长度<=1000; 100%的数据，字符串长度<=5000;
【来源】
MR cheng