Wu Manber多模式匹配算法
AC自动机中,转移的最小单位是一个字符。也就是说,匹配后只能移动一个字符,复杂度是线性的$O(n)$。然而线性并非最快,Boyer-Moore算法在匹配后可以跳过多个字符,比线性还快。据说在实践中,利用Boyer-Moore优化的AC自动机...
AC自动机中,转移的最小单位是一个字符。也就是说,匹配后只能移动一个字符,复杂度是线性的$O(n)$。然而线性并非最快,Boyer-Moore算法在匹配后可以跳过多个字符,比线性还快。据说在实践中,利用Boyer-Moore优化的AC自动机...
断断续续花了三年时间,终于看完这本书,完成了所有习题。看书有很多种看法,开卷有益是一种,自始至终是另一种。有些题目很难,至今AC数只有数十人。据此估计,完整读完这本书的人应该不超过十这个量级。 读书的动机也有很多种,我既不是运动员,也不为面...
Codeforces 123D String 子串函数和:求字符串的所有子串出现次数n代入n(n+1)/2之和。 4.7华丽地处理字符串 后缀数组 题目有些绕,直白地讲就是枚举所有不同的子串,求出现次数,...
AOJ 2292 Common Palindromes 公共回文子串:求两个串的公共回文子串个数。 4.7华丽地处理字符串 后缀数组 拼接后先预处理出后缀数组、高度数组和回文半径数组。其中,每个位置的回文...
POJ 3729 Facer’s string 公共子串: 给出两个字符串A,B,求满足下列条件的C的个数: C是A的子串 C也是B的子串 C加上其在A中的后继字符(若在最尾则加上空格字符)不能够在B中出现 4.7华丽地处理字符...
POJ 3415 Common Substrings 公共子串:统计A和B长度不小于K的公共子串个数。 4.7华丽地处理字符串 后缀数组 将A和B拼接后,累计分属两者的后缀对应的LCP-K+1即为答案,但...
POJ 1509 Glass Beads 降临:在电影《降临》中,七肢桶使用了一种环形语言。给定一个环状字符串,求从哪个字符断开并反转后得到的字符串字典序最小? 4.7华丽地处理字符串 后缀数组 将环切断...
AOJ 1312 Where's Wally 找茬:从大图中找出特定方块小图,旋转翻转皆可。 4.7华丽地处理字符串 字符串匹配 利用循环哈希法计算大图中所有与小图大小一致的子阵的哈希值。 小图旋...
Codeforces 25E Test 出题:众所周知,程序竞赛测试数据越变态越好玩。已知3个字符串会使选手的程序出错,出题者想构造一个超级变态数据同时包含这3个字符串。求该母串最小长度。 4.7华丽地处理字符串 字...
Codeforces 86C Genetic engineering 基因工程:给定m个子串,求构造长n的母串的方案数。母串中每个字符都至少来自一个子串。 4.7华丽地处理字符串 动态规划算法 用AC自动...