标签:字符串

【算法】后缀三兄弟之三——后缀自动机  ——litble

本蒟蒻初识后缀自动机,如有缺漏,请指出,感激不尽。

什么是后缀自动机

后缀自动机是一个有向无环图,节点为状态,有向边为状态转移。其中有一个初始状态可以到达所有状态,若干个结束状态,从初始状态[......]

[继续阅读= ̄ω ̄=]

Read MoreView 1 Comment

【算法】后缀三兄弟之二——后缀数组  ——litble

什么是后缀数组?

假设我们现在有一个字符串"ababa"
我们知道这个数组有一些后缀,分别是(以下后缀i指以i为开头的后缀)

1
2
3
4
5

ababa[......]

[继续阅读= ̄ω ̄=]

Read MoreComment

【题解】洛谷P1470(codevs1052\2778)最长前缀trie树 —by litble

嗯嗯,这题啊,正解应该是trie树。
不过如果你够大佬,比如xzy,就可以用dfs轻松5msA掉。
而本蒟蒻的trie树不仅代码量>大佬xzy,而且还用了44ms。
真是失败。
好吧,思路是建立[......]

[继续阅读= ̄ω ̄=]

Read MoreView 3 Comments

【题解】最长前缀 Longest Prefix 动态规划 LUOGU – 1470

1. 题目

传送门= ̄ω ̄=

2. 题解

[2017年5月16日]
听说能用trie树做。
记忆化非递归式深搜。
设$book(i)$表示状态$i$是否达到过(即前$i$个字符都成功分解)。
枚[......]

[继续阅读= ̄ω ̄=]

Read MoreView 1 Comment

【算法】 kmp 算法

//注:文章是蒟蒻XZY一个字一个字地码出来的,图也是一笔一笔画出来的,要转载一定要说明出处(http://k-xzy.cf)啊/(ㄒoㄒ)/~~!

1. 一些废话

首先说明,本文中的指针都不是真[......]

[继续阅读= ̄ω ̄=]

Read MoreComment

【题解】【AC自动机(裸)】:病毒侵袭(HDU2896)–boshi

这是一道水题

给定几个特征串和几个字符串,求每个字符串中有那几个特征码

思路:

把每个特征串放到TRIE树里(上),用AC机挂着每个串跑一遍即可。但是会出现一种情况:若B串为A串子串,则可能出现[......]

[继续阅读= ̄ω ̄=]

Read MoreComment

【题解】【KMP】:寻找循环节(POJ2406)–boshi

给定一个字符串,求它最多由几个循环节构成。

思路:很自然地想到要求这个字符串最少后移几位后与自己匹配

Read MoreView 1 Comment

【题解】【KMP(裸)】:Oulipo(POJ3461)–boshi

题目是这样的:给你T组数据,每组2个字符串A,B求A在B中出现次数(超过106个字符)

所以只能用KMP

简单介绍一下KMP(刚学)

在字符串匹配的过程中,若使用O(NM)暴力算法,显然会有很多[......]

[继续阅读= ̄ω ̄=]

Read MoreView 1 Comment

【题解】拼数 字符串处理 排序 LUOGU – 1012

//最近没心情刷题,连刷这种水题都没法一遍a,真是……

题目

传送门= ̄ω ̄=

题目描述

设有n个正整数(n≤20),将它们联接成一排,组成一个最大的多位整数。

例如:n=3时,3个整数13[......]

[继续阅读= ̄ω ̄=]

Read MoreComment