| 题目名称 | 2270. [HAOI 2016]找相同子串 |
|---|---|
| 输入输出 | find_2016.in/out |
| 难度等级 | ★★★ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 20 |
| 题目来源 |
 铁策
于2016-04-24加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：96， 提交：232， 通过率：41.38% | ||||
 TimelyRain |
100 | 0.449 s | 56.94 MiB | C++ |
 栋霸霸 |
100 | 0.527 s | 47.29 MiB | C++ |
 AAAAAAAAAA |
100 | 0.589 s | 36.79 MiB | C++ |
 AntiLeaf |
100 | 0.641 s | 51.41 MiB | C++ |
 yourfather |
100 | 0.708 s | 51.02 MiB | C++ |
|
ONCE AGAIN |
100 | 0.718 s | 51.02 MiB | C++ |
|
yourfather |
100 | 0.738 s | 51.02 MiB | C++ |
 YGOI_真神名曰驴蛋蛋 |
100 | 0.785 s | 51.02 MiB | C++ |
 Go灬Fire |
100 | 0.860 s | 39.87 MiB | C++ |
|
Go灬Fire |
100 | 0.865 s | 39.87 MiB | C++ |
| 本题关联比赛 | |||
| 清华集训2017模板练习 | |||
| 关于 找相同子串 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
单调队列+SA
| ||||
|
迷了
| ||||
|
又写了个单串后缀自动机的...
| ||||
|
%%%
 hpy
2017-03-31 20:11
11楼
| ||||
|
| ||||
|
回复 @Cydiater :
后缀自动机的复杂度明明是O(N*字符集大小)的  FoolMike
2017-02-17 12:53
9楼
| ||||
|
直接粘 1712.公共子串 那题的代码
| ||||
|
我$O(N)$的SAM怎么比$O(NlogN)$的SA还慢...
Cydiater
2017-01-21 17:05
7楼
| ||||
|
数组开小直接RE 40分。这数据:惨
| ||||
|
poj上有同类题 poj 3415 你萌代码辣么快，是DC3吗
| ||||
Shirry
sxysxy
Rapiz
_Itachi
TenderRun【题目描述】
给定两个字符串，求出在两个字符串中各取出一个子串使得这两个子串相同的方案数。两个方案不同当且仅当这两个子串中有一个位置不同。
【输入格式】
两行，两个字符串$s_1,s_2$，长度分别为$n_1,n_2$。
【输出格式】
输出一个整数表示答案。
【样例输入】
aabb bbaa
【样例输出】
10
【数据范围】
对于$20\%$的数据，满足$1 \leq n_1,n_2 \leq 500$；
对于$40\%$的数据，满足$1 \leq n_1,n_2 \leq 5000$；
对于$100\%$的数据，满足$1 \leq n_1,n_2 \leq 200000$，字符串中只有小写字母。
【来源】
HAOI2016下午第二题 部分题面由ck进行调整