| 题目名称 | 1973. [HEOI 2015]最短不公共子串 |
|---|---|
| 输入输出 | sus.in/out |
| 难度等级 | ★★★☆ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 10 |
| 题目来源 |
 清羽
于2015-04-28加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：33， 提交：100， 通过率：33% | ||||
 ONCE AGAIN |
100 | 0.174 s | 63.38 MiB | C++ |
 chaijing |
100 | 0.195 s | 1.28 MiB | C++ |
|
yourfather |
100 | 0.246 s | 63.38 MiB | C++ |
 SliverN |
100 | 0.253 s | 62.11 MiB | C++ |
 huhuhuhahaha |
100 | 0.327 s | 32.02 MiB | C++ |
 _Itachi |
100 | 0.346 s | 63.31 MiB | C++ |
|
_Itachi |
100 | 0.357 s | 63.31 MiB | C++ |
 ztx |
100 | 0.432 s | 200.52 MiB | C++ |
 _Horizon |
100 | 0.526 s | 14.90 MiB | C++ |
 zhanggengchen |
100 | 0.556 s | 1.70 MiB | Pascal |
| 关于 最短不公共子串 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
1：暴力trie上枚举
2：DP 3：trie上暴力 4：DP  再见
2017-06-17 12:30
5楼
| ||||
|
记得打上等号，序列自动机是可以取到最后一个的！
| ||||
|
自己写的好像不是标准的序列自动机，有大神可以Hack掉我的代码吗？
| ||||
|
| ||||
|
抄@ztx 的代码...
Orzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz | ||||
FoolMike
SOBER GOOD BOY
Chenyao2333-
【问题描述】
在虐各种最长公共子串、子序列的题虐的不耐烦了之后，你决定反其道而行之。
一个串的“子串”指的是它的连续的一段，例如bcd是abcdef的子串，但bde不是。
一个串的“子序列”指的是它的可以不连续的一段，例如bde是abcdef的子串，但bdd不是。
下面，给两个小写字母串A，B，请你计算：
(1) A的一个最短的子串，它不是B的子串
(2) A的一个最短的子串，它不是B的子序列
(3) A的一个最短的子序列，它不是B的子串
(4) A的一个最短的子序列，它不是B的子序列
【输入格式】
从sus.in中读入。
sus.in中有两行，每行一个小写字母组成的字符串，分别代表A和B。
【输出格式】
输出到sus.out中。
sus.out中输出4行，每行一个整数，表示以上4个问题的答案的长度。如果没有符合要求的答案，输出-1.
【样例输入1】
aabbcc
abcabc
【样例输出1】
2
4
2
4
【样例输入2】
aabbcc
aabbcc
【样例输出2】
-1
-1
2
-1
【数据规模与约定】
对于20%的数据，A和B的长度都不超过20
对于50%的数据，A和B的长度都不超过500
对于100%的数据，A和B的长度都不超过2000