house_cat

分类

ACM(110) JAVA(5) 其他(3) 文(1) 算法导论(2) 计算机图形学(4) 面试(2) 题解(2)

/ 注册

全部文章（共8篇）

[学习笔记]KMP

KMP算法我的腿让我停下，可是心却不允许我那么做。引言字符串匹配。给你两个字符串，寻找其中一个字符串是否包含另一个字符串，如果包含，返回包含的起始位置. char *str = "bacbababadababacambabacaddababacasdsd&q...

学习笔记 KMP 字符串

2018-07-29

0 412

NAIPC2018

NAIPC2018 参考：http://www.cnblogs.com/LQLlulu/p/9513669.html?tdsourcetag=s_pctim_aiomsg https://www.cnblogs.com/clrs97/p/8730429.html?tdsourcetag=s_...

训练记录 tire树字符串

2018-08-26

0 510

[tire+最短路]Bless You Autocorrect!

[tire+最短路]Bless You Autocorrect! Typing on phones can be tedious. It is easy to make typing mistakes, which is why most phones come with an autocorre...

字符串图论最短路 tire树

2018-10-10

0 416

XEN 3166

XEN 3166 这题原题是spj，校oj上只用判断yes no，不过也差不多题意分析之后就是求两个东西：字典序最小的长度为m的子序列同时这个字典序严格大于某个字符串用序列自动机先尽量相同，然后再考虑严格大于 #include <bits/stdc++.h&g...

序列自动机字符串

2019-09-13

0 437

[徐州网络赛]Longest subsequence

[徐州网络赛]Longest subsequence 可以分成两个部分，前面相同，然后下一个字符比对应位置上的大。枚举这个位置用序列自动机进行s字符串的下标转移注意最后一个字符 #include <bits/stdc++.h> const int maxn = 1e6 ...

序列自动机思维字符串

2019-09-13

0 420

[学习笔记]AC自动机

目录概述回顾KMP 字典树insert() 失配指针fail[] 构建函数build() 多模式匹配query() 模板 Aho-Corasick automaton 本文基本上是oiwiki的复制粘贴:https://...

学习笔记 AC自动机字符串

2020-01-27

0 662

[AC自动机]玄武密码

题目描述一个长度为\(N\)的母串，有四个元素分别是:N,S,W,N．有M个长度为100的模式串．现在要求每个模式串的前缀与母串匹配最长长度．输入样例 7 3 SNNSSNS NNSS NNN WSEE 输出样例 4 2 0 题解这是AC自动机的模板题...

字符串 AC自动机

2020-01-29

1 459

KMP算法复杂度证明

引言 KMP算法应该是看了一次又一次，比赛的时候字符串不是我负责，所以学到的东西又还给网上的博客了…… 退役后再翻开看，看到模板，心想这不是\(O(n^2)\)的复杂度吗？有两个循环也不能看做是\(O(n^2)\)的，这要用到摊还分析．模板这里用到的模板是算竞上的 calc...

字符串 KMP

2020-02-03

0 699