首页 > Infinite String Comparision
开通博客写题解
头像 mutou01
发表于 2020-07-12 21:37:20
2020暑期D1-F 思路+证明主为自用，欢迎指正。 https://ac.nowcoder.com/acm/contest/5666/F 思路+证明：a、b字符串可无限复制。若存在a、b可相等则输出‘=’，若不满足则判断‘>’&'<'。字符串比较首先分等长与不等长，由于求的是存 展开全文
去ta的博客 赞 (36) 回复(0) 收起
头像 KeHe
发表于 2020-07-13 10:44:57
题解——我的博客 类比进制中无限循环小数，如 把字符串当做进制数，将串化为无限循环“小数”：则有 另外两种情况同理。 单组数据时间复杂度 #include <bits/stdc++.h> using namespace std; string s, t; int main() { 展开全文
去ta的博客 赞 (28) 回复(1) 收起
头像 RoundMoon
发表于 2020-07-12 15:25:32
代码 #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #pragma war 展开全文
去ta的博客 赞 (16) 回复(0) 收起
头像 Bernard5
发表于 2020-07-13 00:49:52
一开始写了硬模拟，直到比完a.len*b.len/gcd(a.len,b.len)位才结束。然后果不其然被大质数T掉，然后用一种投机取巧的方法过了。 #include <bits/stdc++.h> using namespace std; typedef long long ll; i 展开全文
去ta的博客 赞 (3) 回复(2) 收起
头像 daicon
发表于 2020-09-19 16:31:54
题解 做法 令两循环节分别为 。模拟题意，比较两字符串直到第 个字符为止。 证明 以下记号不区分串和串长 首先给出 Periodicity Lemma： 假设一个字符串 有循环节（不需要是完整循环节） 和 ，并且满足 ，那么 也是一个循环节。 证明见 张晴川知乎专栏叉姐给出了一个数论证 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 11D_Beyonder
发表于 2020-08-10 21:31:42
题目描述   For a string , Bobo defines , which is repeats for infinite times, resulting in a string of infinite length.  Bobo has two strings and . Find 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 zjnu_tjq
发表于 2020-07-24 18:23:15
链接：https://ac.nowcoder.com/acm/contest/5666/F来源：牛客网 题目描述: For a string x, Bobo defines x∞=xxx…, which is x repeats for infinite times, resulting in a 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 牛客99809606号
发表于 2023-04-29 21:55:10
#F Infinite String Comparision# 使用「Z函数」直接将暴力匹配优化成 O(n) 时间 解：比较两个字符串的字典序。使用两根指针总是没错的。 我们知道朴素的解法是：将两个输入字符串都倍增成它们“最小公倍数长度”的字符串，然后用两根指针暴力找第一次不相等的位置，然后比较这个 展开全文
去ta的博客 赞 (0) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”