Absoler

字符串

Java开发(1) MFC(1) 动态规划(5) 图论(7) 基本算法(6) 思维(2) 搜索(7) 数学(2) 数据结构(4) 未归档(29) 杂项(1) 树(2) 模板(3) 真题(9) 计算几何(1)

/ 注册

全部文章 / 字符串（共3篇）

更高效的字符串匹配算法——shift-and

在接触这个算法之前，一直觉得kmp巧夺天工，利用next数组的递推，实现对于模式串任一子串最大相同前后缀的找寻，继而在匹配目标串的过程中，一旦遇到失配情况，可以令匹配起始下标进行合理范围内最大的跳跃，从而将匹配整体复杂度从O(nm)降为O(m+n)。 a b c a b c ........ ...

2020-05-09

0 1198

后缀数组模板

const int N=2e4+10; int n,sa[N],rnk[N],height[N]; char s[N]; //sa数组表示字典序为i的后缀是谁，rnk数组表示某个后缀的排名 void buildSA(int m=128){ int cnt[N],rnk1[N],rnk2[N...

2020-05-09

0 490

回文树模板

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int maxn=3e5+4; struct ...

2020-05-09

0 480