| 题目名称 | 1712. [POJ3415]公共子串 |
|---|---|
| 输入输出 | commonsubstrings.in/out |
| 难度等级 | ★★★ |
| 时间限制 | 5000 ms (5 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 10 |
| 题目来源 |
 cstdio
于2014-09-24加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：61， 提交：118， 通过率：51.69% | ||||
 AntiLeaf |
100 | 0.867 s | 25.28 MiB | C++ |
 _Itachi |
100 | 1.130 s | 25.66 MiB | C++ |
 Marvolo |
100 | 1.402 s | 29.50 MiB | C++ |
 Go灬Fire |
100 | 1.426 s | 24.83 MiB | C++ |
 ONCE AGAIN |
100 | 1.441 s | 26.62 MiB | C++ |
 AAAAAAAAAA |
100 | 1.490 s | 25.68 MiB | C++ |
 可以的. |
100 | 1.657 s | 26.62 MiB | C++ |
 stdafx.h |
100 | 2.052 s | 25.10 MiB | C++ |
|
Go灬Fire |
100 | 2.834 s | 10.06 MiB | C++ |
|
Go灬Fire |
100 | 2.931 s | 52.41 MiB | C++ |
| 关于 公共子串 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
后缀自动机真是劲啊！
| ||||
|
后缀自动机真是劲啊
Go灬Fire
2017-03-08 21:05
7楼
| ||||
|
poj上过了的交到这来40分，而且本机跑没问题
UPD:因为排序用的cnt数组实际上下标访问时可以大于200的，所以把它也开成maxn就过了...(为了省内存都不知道自己怎么死的... _Itachi
2017-02-15 06:04
6楼
| ||||
|
突然发现原来是lb打成了la，导致wa了= =还以为自己跑SAM的思想错了= =
 再见
2016-11-12 21:36
5楼
| ||||
|
我是sb，让merge给挂了，真是智障！
| ||||
|
撸一发SAM（精疲力竭QAQ
| ||||
|
回复 @cstdio :
用 c++ 交可过  ztx
2014-12-24 17:34
2楼
| ||||
|
在这只能用lld，在POJ上只能用I64d……简直了……
| ||||
FoolMike
cstdio1712. [POJ3415]公共子串
★★★ 输入文件：commonsubstrings.in
输出文件：commonsubstrings.out
简单对比时间限制：5 s 内存限制：256 MiB
【题目描述】
字符串T的一个子串定义为：
T(i,k)=T[i]T[i+1]...T[i+k-1]，1<=i<=i+k-1<=|T|。
给出两个字符串A,B，一个整数K，我们定义S是一个由三元组构成的集合：
S={(i,j,k)|k>=K,A(i,k)=B(j,k)}。
你需要对于A,B,K，给出|S|的值。
【输入格式】
输入包含多组数据。
每组数据的第一行是一个正整数K，接下来是两行，分别是字符串A和B。输入结束标志为K=0。
【输出格式】
对每组数据输出一行一个整数，即|S|。
【样例输入】
2
aababaa
abaabaa
1
xx
xx
0
【样例输出】
22
5
【提示】
1<=|A|,|B|<=10^5
1<=K<=min{|A|,|B|}
A和B中仅含小写字母。