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

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

2017-06-15阅读(4920)评论(1)

在Mac等*nix下编译Windows动态链接库或可执行文件，常见方法是虚拟机。然而虚拟机操作不流畅，来回拷贝源码不方便。虽然虚拟机自动将宿主目录挂载为磁盘分区，但cmd实际无法cd进去： 更好的方法是直接利用Wine容器中的编译链，一边开...

2017-03-27阅读(5224)评论(1)

一些使用了matplotlib的脚本在启动的时候就会在dock上显示一个小火箭： 如果脚本在执行很耗时的操作，比如训练，则UI长期得不到响应，这个小火箭就会一直瞎蹦跶，怪讨厌的。解决方法有两个： 配置文件解决 vi /path/t...

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

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

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

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

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

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

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

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

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

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

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

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

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

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