algorithm - ACM 问题 : Number of distinct substrings of long string-6ren

algorithm - ACM 问题 : Number of distinct substrings of long string

转载作者：塔克拉玛干更新时间：2023-11-03 04:51:40

25

4

<分区>

这道题取自往年的acm竞赛。问题:

给定字符串 p长度k <= 1000
这个字符串重复无限次，现在我们先取 n < 10^9人物。让我们调用结果字符串 s .

任务是找到字符串 s 的唯一子串的计数.

计算不同子串的传统方法是后缀 + lcp 数组，但我们需要 O(n) 来构造它们(使用最快且相当复杂的构造算法)。并且在构造完这些数组之后我们还需要做很多进一步的处理，所以我认为这个解决方案不符合时间要求。

我看过问题分析，但我完全不明白。当然它工作得很好，但他们是如何做到的呢？在这里:

如果 p = tt...t对于一些字符串 t , 替换 p与 t .现在让我们假设 p 是非周期性的。
f(n) — s 前缀中唯一子串的计数长度n .
我们假设 n > 2k .然后 f(n) = f(n-1)+k . <- 为什么？这背后的逻辑是什么？

证明:

让t是 s 的后缀.
如果 |t| <= n - k , 然后 l也包含在左侧 k 个符号上的 s 中。
- 如果|t| > n - k , 然后 l仅作为后缀包含在 s 中。
n<=2k无论如何都能解决问题。

非常感谢对此问题分析或您自己的解决方案的任何解释!我不明白我怎么能想出这个函数 f()。这几天一直在思考这个问题。

25

4

0

文章推荐： javascript - React 中具有多个标准的复杂结果过滤

文章推荐： java - SetVisible(false) 更改面板中组件的布局

文章推荐： java - 我怎样才能知道从特定日期过去了多少天？

MySQL:如果第一个条目选择“Where Distinct”，则在查询中不“Distinct”
我有一个包含电子邮件、IP、州、城市、时间戳、ID 列的表我需要按州分组计算电子邮件和 IP 的不同位置所以当我运行 MYSQL 查询时， select State, City ,count(di
mysql - sql中select distinct id和select distinct *的区别
我试过 select distinct ID from DB.TABLE; 它返回所有记录中的唯一 ID。 select distinct * from DB.TABLE; 它将通过比较所有列
sql - 使用 DISTINCT 子句过滤数据但仍拉取其他非 DISTINCT 字段
我正在尝试在 Postgresql 中编写一个查询，该查询提取一组有序数据并按不同的字段对其进行过滤。我还需要从同一表行中提取其他几个字段，但需要将它们排除在不同的评估之外。示例: SELECT
sql - Postgres DISTINCT 与 DISTINCT ON 之间有什么区别？
我有一个使用以下语句创建的 Postgres 表。该表由另一个服务的数据转储填充。 CREATE TABLE data_table ( date date DEFAULT NULL,
mysql - 根据同一行中的另一个 DISTINCT 列获取 DISTINCT 列
我在一个名为 products 的表中有 4 列 id|p_name| p_img | 1 | Xs | xsmax.png | 2 | Xs | xr.png |
mysql - 在 DISTINCT 条件中选择 DISTINCT 列
当它的状态仅为"is"时，我想从“num”中选择不同的值，而不是立即包括“否”？表: +--------+-----+--------+ | id | num | status | +---
php - 如何同时使用 DISTINCT 行和非 DISTINCT 行
全部!今天我有一个棘手的问题要给你，我想使用 select DISTINCT 语句来选择一个需要不同的行，但也在同一个语句中(或者我尝试过的方式？)一个没有的行't/不能区分。我想要的结果是每个类名中
c# - IQueryable.Distinct() 与 List.Distinct()
我有一个正在使用 Distinct() 的 linq 查询。如果我只是调用 Distinct() 而没有转换为列表，那么它不会返回不同的列表 - 它仍然包含重复项。但是，如果我转换为 List 并然
linq - 我应该使用 .ToList().Distinct() 还是 .Distinct().ToList()？
说到性能，我应该使用 .ToList().Distinct() 还是 .Distinct().ToList() ？两种扩展方法是否生成相同的 SQL 查询？看起来第二种方法应该表现更好，但这是真的
sql - 如何在SQL Server 20008R2中重写IS DISTINCT FROM和IS NOT DISTINCT FROM？
如何在不支持 SQL Server 2008R2 的 SQL 实现中重写包含标准 IS DISTINCT FROM 和 IS NOT DISTINCT FROM 运算符的表达式？最佳答案 IS DI
mysql - 为什么 Distinct * 不起作用但 count(Distinct *) 起作用？
有一张 table (在 HIVE) 示例 - meanalytics.key2_master_ids 该表有 6 列(cmpgn_id、offr_id、exec_id、creatv_id、cmpl_
mysql-workbench - 如何将 DISTINCT 数据导出到 DISTINCT 文件
SELECT * FROM `amc_info` WHERE department =' ( SELECT DISTINCT department ) into outfile = 'Differe
elasticsearch - 在Elasticsearch中可以计算 “distinct sum”和 “distinct average”吗？
如何在Elasticsearch中计算“不同的平均值”？我有一些这样的非规范化数据: { "record_id" : "100", "cost" : 42 } { "record_id" : "200
sql-server - 在一列上选择 Distinct 并消除 Select Distinct 中的空值？
关注这个question我有... ID SKU PRODUCT ======================= 1 FOO-23 Orange 2 BAR
mysql - 为什么 DISTINCT 使这个查询比没有 DISTINCT 花费的时间长 10 倍？
我有这个 mysql 查询: SELECT DISTINCT post.postId,hash,previewUrl,lastRetrieved FROM post INNER JOIN (tag a
mysql - 我们可以对 group_concat(distinct somefield) 做一个 DISTINCT 吗？
http://sqlfiddle.com/#!2/37dd94/17 如果我执行 SELECT DISTINCT，我得到的结果与只执行 SELECT 的结果相同。在查询结果中，您将看到两个包含 Di
mysql - func.count(distinct(...)) 不会给出与 distinct().count() 相同的结果
我有一列包含空条目，例如此列中的可能值为 None, 1, 2, 3 当我使用 session.query(func.count(distinct(Entry.col))).scalar() 计算列中
php - 在 mysql 中选择 distinct 和 count distinct
这是否可能从表列中选择不同的行并计算单个查询中每个不同字段的重复行 $sql = "SELECT DISTINCT location and COUNT(DISTINCT location)
mysql - count(distinct col_name) 与计算 select distinct 查询的行数不同吗？
我在 MySQL 数据库中有一个包含 1100 万行的表。其中一列是个人身份证号码。人们在表中被多次列出，我想知道有多少个唯一的个人 ID 号码。然后创建一个包含这些唯一数字的表格。当我计算列中不同的
sql - 为什么 SELECT DISTINCT 返回的行数与 COUNT(DISTINCT) 不同？
我刚刚注意到我的 Informix SQL 列(在同一个表中)的某些上有些奇怪。当我执行此查询时 SELECT DISTINCT colName FROM myTable 例如，我得到 40 行。但

首页

博学

6Ren·AI

商城

algorithm - ACM 问题 : Number of distinct substrings of long string