Day3

【作文】
题意:求一个字符串的子串,使其在字符串中至少出现三次,分别是前缀、后缀、以及非前、后缀。
字符串匹配,考虑KMP,分别将字符串删去前一个字符和后一个字符,将这两个串进行匹配,求出前缀、后缀的可行长度。对原串求next数组,在可行前后缀的位置求答案。
正解是二分,哈希暴力求出前后缀的可行长度,二分这些长度暴力判断。
【智能机器人】
题意:用多个机器人遍历一棵树,使消耗的代接最小。
首先,一个明显的结论,如果从某个节点往下走去了多于1个机器人,那么它们绝对不会再回头.如果它们有一个回头,则令这个机器人处于该节点的父节点不动,令另外一个机器人先走这个机器人走的路线然后在走自己的路线,就会更优!
令f[x][i]表示i个机器人走完x子树的最优值。g[x]表示只用一个机器人走x子树(即机器人要回到x点)。可得:
f[x][i] = min(f[x][i - j] + f[y][j] + w * j)。
f[x][i] = min(g[x] + f[y][i] + w * i)。
f[x][i] = min(f[x][i] + g[y] + w * 2)。
g[x] = g[x] + g[y] + w * 2。
【大都市】
题意:给定一棵树,从1结点出发,每次修改一条边,求到某个点的路径上经过的未修改路径树。
可以发现,如果修改一条边,则这条边所连接的子树答案都会改变(-1)。联想到DFS序,在DFS序中,一个点的子树是一段连续的区间,那么,可以使用数据结构来维护修改,如树状数组,线段树。

7月17日备战Noip2017暑假集训2(A) 监听还原【KMP】

【问题描述】

Alice和Bob正在悄悄地给对方发信息,信息都是由英文小写字母组成的,他们约定,所有的字母都得经过一个字母表进行变换,以防泄漏。另一方面John却在监听。

John发现,Alice和Bob通信的时候,总是先发送加密后的密文,然后紧接着发送原文。

但是Alice和Bob似乎也意识到了似乎有人监听,有时候会随意中断了他们的通信。不过每次都是在发送完密文之后才停止传送的。也就是说,John截获到的信息是密文的全文以及前一部分原文。原文可能一个字符都没有,也可能原文的全文都被截获。

现在John比较头疼,他虽然已经得到了他们两个人通信的加密字母表,但是分不清楚什么地方是密文和明文的分界线。你能帮他还原回完整的传输内容吗?

如果有多种可能时,John认为那个最短的信息才是原始的。

【输入格式】

第一行是密码表格,包含26个小写字母,依次表示a-z加密后的字母。

第二行是John截获到的通信信息。

【输出格式】

包含一行,表示还原后的通信信息。

【输入输出样例一】

recover.in recover.out
abcdefghijklmnopqrstuvwxyz

abcdab

abcdabcd

 

【输入输出样例二】

recover.in recover.out
qwertyuiopasdfghjklzxcvbnm

qwertabcde

qwertabcde

【数据规模】

    对于30%的数据:L<=100。

对于100%的数据:通信长度L<=100000。

继续阅读7月17日备战Noip2017暑假集训2(A) 监听还原【KMP】

KMP(字符串匹配)

KMP算法是一种高效的字符串匹配算法。通常,在求两个字符串是否匹配是,都是枚举一个字符串的开头与另一个字符串匹配, 假如 A 串长度为 n , B 串长度为 m , 那么这种方法的复杂度是 O(nm)的。而KMP能在O(n)的时间内完成。

【KMP思想】

如图,假设有A,B两个字符串要求匹配,当匹配到A[i]、B[j]时,A[1..i-1]与B[1..j-1]完全匹配,但A[i]!=B[j]。通常,遇到这种情况,都是再枚举开头,重新进行匹配,但是这会浪费很多时间。仔细观察,发现B串的a部分与b部分完全相同,那么可以适当减少j的值(相当于把B串往后移动),那么匹配便可以继续进行。如下图。

显而易见,j减少的多少与A无关,只与B有关。 我们完全可以预处理出这样一个数组 next[j], 表示当匹配到 B 数组的第 j 个字母而第 j +1个字母不能匹配了时, 新的 j 最大是多少。 next[j] 应该是所有满足 B[1..k]= B[ j- k+1... j]的k (k < j) 的最大值。

于是容易得出KMP的代码:


1
2
3
4
5
6
7
8
9
void KMP()  {
    int j = 0;
    for (int i = 1;i <= m; i++)  {
        while (j && b[i] != a[j + 1]) j = next[j];
        if (b[i] == a[j + 1]) ++j;
        if (j == n)
            j = next[j];
    }
}

最后的 j=next[j]是为了让程序继续做下去, 因为我们有可能找到多处匹配。

那么next数组要怎么求呢?

假设我们现在已经求得next[1]、next[2]、……next[i],分别表示长度为1到i的字符串的前缀和后缀最大公共长度,现在要求next[i+1]。

  1. 如果位置i+1和位置next[i+1]处的两个字符相同(下标从零开始),则next[i+1]等于next[i]加1。
  2. 如果两个位置的字符不相同,我们可以将长度为next[i]的字符串继续分割,获得其最大公共长度next[next[i]],然后再和位置i的字符比较。这是因为长度为next[i]前缀和后缀都可以分割成上部的构造,如果位置next[next[i]]和位置i的字符相同,则next[i+1]就等于next[next[i]]加1。如果不相等,就可以继续分割长度为next[next[i]]的字符串,直到字符串长度为0为止。

怎么这个预处理过程跟前面的 KMP 主程序这么像呢? 其实, KMP 的预处理本身就是一
个 B 串“自我匹配” 的过程。


1
2
3
4
5
6
7
8
9
void Find_next()  {
    int j = 0;
    next[1] = 0;
    for (int i = 2;i <= n; i++)  {
        while (j && a[j + 1] != a[i]) j = next[j];
        if (a[j + 1] == a[i]) j++;
        next[i] = j;
    }
}

最后为什么KMP的代码会是O(n)的呢?

我们从上述程序的 j 值入手。 每一次执行 while 循环都会使 j减小( 但不能减成负的) , 而另外的改变 j 值的地方只有一处。 每次执行了这一处, j 都只能加 1; 因此, 整个过程中 j 最多加了 n 个 1。 于是, j 最多只有 n 次减小的机会(j 值减小的次数当然不能超过 n , 因为 j 永远是非负整数) 。 这告诉我们, while 循环总共最多执行了 n 次。 按照摊还分析的说法, 平摊到每次 for 循环中后, 一次 for 循环的复杂度为O(n)
整个过程显然是O(n) 的。 这样的分析对于后面next数组预处理的过程同样有效, 同样可以得到预处理过程的复杂度为 O(n)。
完整代码如下: 继续阅读KMP(字符串匹配)

字符串编码

字符串编码

day1里的T1。

字符串哈希+暴力。

对S,T这两个字符串进行哈希,令数字0...25表示小写字母a...z,设f[i][j]表示串S前i位的j字符的哈希值,g[i]表示串T的i字符的哈希值。那么对于一个从x起始的S的子串,若选中字符i,j,此子串与T匹配的充要条件是S[x+|T|-1][i]-S[x-1][i]=T[j]且S[x+|T|-1][j]-S[x-1][j]=T[i]。

在判断时只需枚举每个起始位置,枚举两个字符i,j,判断选中i,j能否使S的子串与T匹配即可。

时间复杂度

继续阅读字符串编码