上一页 1 ··· 58 59 60 61 62 63 64 65 66 ··· 87 下一页
2018年8月19日
Maximum repetition substring POJ - 3693（重复次数最多的连续重复子串）
摘要： 这题和SPOJ - REPEATS 一样 代码改一下就好了 这个题是求这个重复子串，还得保证字典序最小 巧妙运用sa 看这个 https://blog.csdn.net/queuelovestack/article/details/53035903 很清晰 阅读全文
posted @ 2018-08-19 18:49 WTSRUVF 阅读(262) 评论(0) 推荐(0)
Repeats SPOJ - REPEATS（重复次数最多的连续重复子串）
摘要： 论文题例8 https://blog.csdn.net/queuelovestack/article/details/53031731这个解释很好 其实，当枚举的重复子串长度为i时，我们在枚举r[i*j]和r[i*(j+1)]的过程中，必然可以出现r[i*j]在第一个重复子串里，而r[i*(j+1) 阅读全文
posted @ 2018-08-19 16:47 WTSRUVF 阅读(593) 评论(0) 推荐(0)
树状数组求逆序对
摘要： 1、什么是逆序数？ 2、用树状数组求逆序数的总数 2.1该背景下树状数组的含义 2.2如何使用树状数组求逆序数总数 2.3 C++实现代码 1、什么是逆序数？ 在一个排列中，如果一对数的前后位置与大小顺序相反，即前面的数大于后面的数，那么它们就称为一个逆序。一个排列中逆序数的总数就是这个排列的逆序数 阅读全文
posted @ 2018-08-19 10:55 WTSRUVF 阅读(683) 评论(0) 推荐(0)
2018年8月18日
Extend to Palindrome UVA - 11475（补成回文串）
摘要： 题意： 就是用最少的字符把原字符串补成回文串 解析： emm/。。。/网上都是用kmp和后缀数组做的 我没想到这俩的思路。。。emmm。。。 想到了exkmp的 就是原串和逆串匹配一下 注意要保证这个匹配的最大长度 要到原串的结尾 阅读全文
posted @ 2018-08-18 20:09 WTSRUVF 阅读(306) 评论(0) 推荐(0)
每个字符串至少出现两次且不重叠的最长子串
摘要： Relevant Phrases of Annihilation SPOJ - PHRASES https://cn.vjudge.net/problem/SPOJ-PHRASES 呵。。。呵。。。 我觉得我写的很对呀。。。 真是的。。。 这么漂亮。。。 行吧。。一下午没检查出来哪里有问题 真是的 阅读全文
posted @ 2018-08-18 18:06 WTSRUVF 阅读(358) 评论(0) 推荐(0)
Life Forms POJ - 3294（不小于k个字符串中的最长子串）
摘要： 题意： 求不小于字符串一半长度个字符串中的最长字串 解析： 论文题例11 将n个字符串连起来，中间用不相同的且没有出现在字符串中的字符隔开， 求后缀数组， 然后二分答案变为判定性问题， 然后判断每组的后缀是否出现在不小于 k 个的原串中， 这个做法的时间复杂度为O（nlogn） 阅读全文
posted @ 2018-08-18 12:35 WTSRUVF 阅读(215) 评论(0) 推荐(0)
Common Substrings POJ - 3415(长度不小于k的公共子串的个数)
摘要： 题意： 给定两个字符串A 和 B， 求长度不小于 k 的公共子串的个数（可以相同） 分两部分求和sa[i-1] > len1 sa[i] < len1 和 sa[i-1] < len1 sa[i] > len1 阅读全文
posted @ 2018-08-18 09:59 WTSRUVF 阅读(282) 评论(0) 推荐(0)
2018年8月17日
Long Long Message POJ - 2774（最长公共子串）
摘要： 题意： 给你两串字符，要你找出在这两串字符中都出现过的最长子串 解析： 先用个分隔符将两个字符串连接起来，再用后缀数组求出height数组的值，找出一个height值最大并且i与i-1的sa值分别在两串字符中就好了 阅读全文
posted @ 2018-08-17 21:39 WTSRUVF 阅读(329) 评论(0) 推荐(0)
Power Strings POJ - 2406（next水的一发 || 后缀数组）
摘要： 后缀数组专题的 emm。。 就next 循环节。。/ 有后缀数组也可以做 从小到大枚举长度i，如果长度i的子串刚好是重复了len/i次，应该满足len % i == 0和rank[0] - rank[i] == 1（整个串的等级比 i位置开始的后缀的等级大1 （i位置开始的后缀即为比总串低一个等级的 阅读全文
posted @ 2018-08-17 18:44 WTSRUVF 阅读(148) 评论(0) 推荐(0)
Distinct Substrings SPOJ - DISUBSTR(后缀数组水题)
摘要： 求不重复的子串个数 用所有的减去height就好了 推出来的。。。 阅读全文
posted @ 2018-08-17 18:19 WTSRUVF 阅读(185) 评论(0) 推荐(0)
上一页 1 ··· 58 59 60 61 62 63 64 65 66 ··· 87 下一页