2018-02-03阅读(22399)评论(2)

AC自动机中，转移的最小单位是一个字符。也就是说，匹配后只能移动一个字符，复杂度是线性的$O(n)$。然而线性并非最快，Boyer-Moore算法在匹配后可以跳过多个字符，比线性还快。据说在实践中，利用Boyer-Moore优化的AC自动机...

2017-02-13阅读(8676)评论(8)

断断续续花了三年时间，终于看完这本书，完成了所有习题。看书有很多种看法，开卷有益是一种，自始至终是另一种。有些题目很难，至今AC数只有数十人。据此估计，完整读完这本书的人应该不超过十这个量级。 读书的动机也有很多种，我既不是运动员，也不为面...

2017-02-12阅读(5934)评论(0)

Codeforces 123D String  子串函数和：求字符串的所有子串出现次数n代入n(n+1)/2之和。 4.7华丽地处理字符串  后缀数组  题目有些绕，直白地讲就是枚举所有不同的子串，求出现次数，...

2017-02-11阅读(5228)评论(0)

AOJ 2292 Common Palindromes  公共回文子串：求两个串的公共回文子串个数。 4.7华丽地处理字符串  后缀数组  拼接后先预处理出后缀数组、高度数组和回文半径数组。其中，每个位置的回文...

2017-02-10阅读(4980)评论(0)

POJ 3729 Facer’s string  公共子串： 给出两个字符串A,B,求满足下列条件的C的个数: C是A的子串 C也是B的子串 C加上其在A中的后继字符(若在最尾则加上空格字符)不能够在B中出现 4.7华丽地处理字符...

2017-02-09阅读(5630)评论(0)

POJ 3415 Common Substrings  公共子串：统计A和B长度不小于K的公共子串个数。 4.7华丽地处理字符串  后缀数组  将A和B拼接后，累计分属两者的后缀对应的LCP-K+1即为答案，但...

2017-02-08阅读(5088)评论(0)

POJ 1509 Glass Beads  降临：在电影《降临》中，七肢桶使用了一种环形语言。给定一个环状字符串，求从哪个字符断开并反转后得到的字符串字典序最小？ 4.7华丽地处理字符串  后缀数组  将环切断...

2017-02-07阅读(4882)评论(0)

AOJ 1312 Where's Wally  找茬：从大图中找出特定方块小图，旋转翻转皆可。 4.7华丽地处理字符串  字符串匹配  利用循环哈希法计算大图中所有与小图大小一致的子阵的哈希值。 小图旋...

2017-02-06阅读(4542)评论(0)

Codeforces 25E Test  出题：众所周知，程序竞赛测试数据越变态越好玩。已知3个字符串会使选手的程序出错，出题者想构造一个超级变态数据同时包含这3个字符串。求该母串最小长度。 4.7华丽地处理字符串  字...

2017-02-05阅读(4917)评论(0)

Codeforces 86C Genetic engineering  基因工程：给定m个子串，求构造长n的母串的方案数。母串中每个字符都至少来自一个子串。 4.7华丽地处理字符串  动态规划算法  用AC自动...