SHIVAKASU

一、算法背景Manacher算法，中文名马拉车算法，用以解决求字符串中的最长回文子串。传统的寻找最长回文子串的方法是从左到右遍历字符串的每个字符，同时以每个字符为回文中心向左右两侧扩散寻找，当字符串中存在大量回文子串，比如在极端情况下 $“aa…aa”$ ，算法的时间复杂度是 $O(N^2)$ 。而Manacher算法能够把寻找最长回文子串的时间复杂度降到 $O(N)$ 。 二、字符串预处理假设要处理的字符串是 $“abbabb”$ ，由于回文串有奇回文和偶回文，比如 $“bab”$ 是奇回文， $“abba”$ 是偶回文，奇回文的对称轴是一个字符，偶回文的对称轴是两个字符，为了消除这种差异，首先要对字符串预处理，在每个字符的两侧都添加占位符，比如 $“\sharp”$ ，原来的字符串就变成了 $“\sharp a\sharp b\sharp b\sharp a\sharp b\sharp b\sharp ”$ 。对于其中的每个回文串，预处理相当于在每个字符的右侧添加占位符，变成偶回文，再在整体回文串的左侧添加一个占位符，变成奇回文。比如上述两个回文串变成了 $“\sharp b\sh ...

一、问题描述输入原字符串(String)和子串(Pattern)，找到子串在原字符串中第一次出现的位置，两个字符串分别命名为 $s$ 和 $p$ 二、暴力检索暴力检索(Brute Force)是最简单的匹配方法，首先把 $s$ 和 $p$ 左端对齐，从两个字符串头部开始逐位匹配，匹配失败后将 $p$ 右移一位，从 $p$ 的头部和 $s$ 的对应位置重新匹配。 最坏情况下，假设 $s=“xx….xy”$ ，长度为 $N$ ， $p=“xx…xy”$ ，长度为 $M$ ，每次匹配都需要比较全部 $M$ 个字符，而只有最后一次匹配才能匹配成功，所以时间复杂度是 $O(M\times N)$ 三、KMP算法KMP算法全称是Knuth-Morris-Pratt字符串查找算法，算法的核心思想是利用最大相同前缀后缀长度来减少匹配次数。例如 $ABCAB$ 的前缀有 $A$ 、 $AB$ 、 $ABC$ 、 $ABCA$ 四个，后缀有 $B$ 、 $AB$ 、 $CAB$ 、 $BCAB$ 四个，那么他的最大相同前缀后缀就是 $AB$ ，最大相同前缀后缀长度是2。所以对于字符串 $str[0..n] ...

第一章 栈和队列1.1 $getmin$ 栈用两个栈， $A$ 正常使用， $B$ 在 $A$ 的 $push$ 和 $pop$ 时保持栈顶是 $A$ 的最小值 1.2 两个栈组成队列两个栈方向相反， $A$ 压栈代表入队， $B$ 退栈代表出队，当 $B$ 为空时，把 $A$ 反向导入 $B$ 问题是不能保证出队 $O(1)$ ？ 1.3 用递归函数和栈逆序一个栈两个递归函数， $A$ 递归 $pop$ 栈中所有元素，返回最后一个元素，再把剩下的 $push$ 回去。 $B$ 递归调用 $A$ ，把 $A$ 返回的 $push$ 回去 1.4 猫狗队列一个队列存猫，一个队列存狗，一个数组用01标注存放顺序 1.5 用一个栈实现另一个栈的排序把A栈的依次 $pop$ ，如果比B栈顶大就 $push$ 到 $B$ ，否则把 $B$ $pop$ 并 $push$ 回 $A$ 直到比 $B$ 栈顶大，核心就是利用两个栈来回倒，用一个临时变量做插入排序 1.6 用栈求解汉诺塔递归思路：把 $1\sim N$ 从左移动到右，相当于把 $1\sim(N-1)$ 从左移动到中，再把 $N$ 从左 ...

  1、python中的函数装饰器(Function decorator)用来“标记函数”，以某种方式增强函数的行为，其实就是一种语法糖(syntactic sugar)，用来简化复杂的代码。如下： 可以用装饰器实现函数的替换，虽然这么做没什么意义：>>> def deco(func):... def inner():... print('running inner()')... return inner #1>>> @deco... def target(): #2... print('running target()')...>>> target() #3running inner()>>> target #4<function deco.<locals>.inner at 0x10063b598> 还可以用作注册函数，对于新增的函数，只需要添加装饰器，而不用手动进行注册：registry = [ ...

  1、在python中，函数是一等对象(first-class object)，一等对象的特征有： 在运行时创建 能赋值给变量或数据结构中的元素 能作为参数传给函数 能作为函数的返回结果 接受函数为参数或把函数作为结果返回的函数又叫高阶函数(higher-order function)，常见的高阶函数例如python内置的sorted，其接收一个参数key，当想根据长度排序时，可以写成sorted(xxx,key=len)，这就是把len()函数作为参数传给sorted()。在函数式编程范式中，常用的高阶函数有map、filter、reduce和apply，然而在python中不常用这些函数，因为已经有了更简单的替代方式。 map函数用来求一个序列或者多个序列进行函数映射之后的值，filter函数用来过滤掉序列中不符合函数条件的元素，二者完全可以用列表推导式替代，对应for循环和if条件判定。 reduce函数用来对一个序列进行压缩运算，在python3中已经移到了functools模块，该方法最常用于序列求和，因此可以用python内置的sum函数替代。 ...

  1、collections.abc模块中有Mapping和MutableMapping两个抽象基类，它们的作用是为dict和其他类似的类型定义形式接口。   2、标准库里的所有映射类型都是利用dict实现的，只有可散列(hashable)的数据类型才能用作这些映射里的键。如果一个对象是可散列的，那么在这个对象的生命周期中，它的散列值是不变的，而且这个对象需要实现__hash__()方法进行散列，也要实现__eq__()方法进行键的比较。python的原子不可变类型(str、bytes和数值类型)是可散列的，一个元组是可散列的当且仅当其包含的元素都是可散列的。所以严格来说不可变类型不都是可散列的，元组不一定。   3、和列表推导式类似，字典也有推导构建法：   4、处理字典可能找不到键的情况： 使用setdefault()方法，如下图。这样做的好处是减少了查询字典的次数，如果键不存在，不使用setdefault()就需要查三次字典。 使用collections.defaultdict字典，提供 ...

  1、python标准库用C实现了丰富的序列类型： 容器序列(Container sequences)：list、tuple、collections.deque这些序列能存放不同类型数据。 扁平序列(Flat sequences)：str、bytes、bytearray、memoryview、array.array这些序列只能容纳一种类型。 可变序列(Mutable sequences)：list、bytearray、array.array、collections.deque、memoryview这些序列可以原地修改。 不可变序列(Immutable sequences)：tuple、str、bytes这些序列不能原地修改。   下图是序列对象的继承关系，箭头从子类指向父类，可以看到可变对象之所以能够修改是因为实现了__setitem__、__delitem__等方法。   2、python会忽略代码里[]、()、{}中的换行，所以写列表推导时直接回车换行，不用加续行符“\”。   3、当使用“*” ...

  这一章写的是python的特殊方法(special method)，又叫作魔术方法(magic method)。最常见的就是面向对象编程时的初始化方法__init__，这类方法的特点有： 方法名首尾有两个下划线。 所有特殊方法都是python内置的，使用时只需要在类里重写，最好不要自己定义新的特殊方法。 特殊方法都与特殊操作绑定，不需要显式调用。如__init__与对象初始化绑定，__len__与len()方法绑定，__add__与+运算绑定。   部分特殊方法如下，首先是与运算符无关的特殊方法： 然后是与运算符有关的特殊方法：   __repr__和__str__都是用于定义对象的字符串表示形式。区别是前者用于在命令行直接输入一个对象时返回的字符串，后者是调用str()方法或print()时返回的字符串。如果只想实现其中一个特殊方法，就实现__repr__，因为没有__str__时解释器会自动调用__repr__。   __bool__用于定义一个对象的真值，如果对象需要参与条件判定的话，可以用b ...

1 文本相似度  文本的相似度依靠距离函数度量，距离函数应该是对称的，即不受参数顺序影响，并且应该满足三角不等式： distance(a,c)\leq distance(a,b)+distance(b,c)  常见的距离函数如下： 海明距离(Hamming distance)：对于相同长度的字符串，定义它们之间的距离为他们拥有不同字符的位置的个数。 编辑距离(Edit distance)：使两个字符串相同而在其中任何一个字符串上进行字符插入、删除和替换操作的最少次数。如“color”和“colour”的编辑距离是1。编辑距离是处理语法错误的首选模型。 最长公共子序列(longest common subsequence, LCS)：如“survey”和“surgery”的最长公共子序列是“surey”。 余弦相似度：第三章提到过。 类似度(resemblance)：两个文档词汇表的重合度。定义 W(d_j) 是 d_j 中所有不同词的集合，两个文档的类似度定义为：R(d_i,d_j)=\frac{|W(d_i)\cap W(d_j)|}{|W( ...

1 定义  检索评价针对信息检索系统响应用户查询的返回结果，系统化地给出了一个量化的指标。这个指标应该和检索结果与用户的相关性直接联系。计算这个指标的通常方法是，对于给定的一组查询，比较由系统产生的结果和由人产生的结果。这里的检索评价仅针对检索系统的结果质量，不考虑界面设计、系统性能等因素的影响。 2 检索指标2.1 精度和召回率  精度(Precison)是检出文档中相关文档的比例，召回率(Recall)是相关文档集中被检出的比率。将相关文档集记作 R ，系统得出的结果集为 A ，则： 精度=p=\frac{|R\cap A|}{|A|}召回率=r=\frac{|R\cap A|}{|R|}以横坐标为召回率，纵坐标为精度可绘制精度-召回率曲线，曲线下面积(Area Unser the Curve, AUC)可用于评估不同答案集的质量，面积越大表明质量越好。   缺点： 召回率无法准确估计。 精度和召回率是相关联的指标，将二者结合为单一指标会更合适。 只能度量批处理状态下对一组查询进行处理的结果。 对于只需要弱偏序关系的系统 ...