字符串匹配-KMP 一、传统匹配。 逐个匹配,若匹配失败,文本串换下一个字符,模式串从头与其再逐个匹配.......时间复杂度O(n*m). 二、kmp匹配 若模式串第i+1位匹配失败,文本串换下一个字符,模式串从第fail[i]+1位与其逐个匹配......时间复杂度O(n). 三、fail数组 理解这个数组即理解了kmp算法   注意到最后5个字符,分别与该字符串的第0,1...4位是一样的,所以他们的fail数组也是0,1,2,3,4。   fail[i]与fail[i-1]有关。像第6位…

2017年9月28日 0条评论 2点热度 阅读全文

题目链接: http://poj.org/problem?id=1094 题意: 给出一连串关系,判断3个问题: 1.有唯一解并输出 2.是否有环 3.没有唯一解 注意1,3还要输出在第几个关系可以判断出来,可知3需要判断到最后,而1可能不需要。 AC代码: #include <iostream> #include <algorithm> #include <cstring> #include <cstdio> #include <map> using n…

2016年9月15日 0条评论 2点热度 阅读全文

题目的分析被说得有点绕。自己理解是这样,首先由题目我们知道选择的区间都是相互不相交的,除这之外,我们的目标是尽量的让选择的区间达到最大化。 所以我们可以先对齐排序,因为输入是随机的。假设每个区间表示为(x,y)我们可以选择按照x排序所有区间,也可以选择按照y来排序所有区间。而不管选择哪一个来排序,其原理和本质都一样,都是为了方便操作,将其有序化。 我们这里选择按照y来排序,排序完后有y1 <= y2 <= y3....... 现在我们讨论x1 x2 .... 当x1 > x2时,区间被x2这个区间…

2013年4月5日 0条评论 2点热度 阅读全文

题目的分析被说得有点绕。自己理解是这样,首先由题目我们知道选择的区间都是相互不相交的,除这之外,我们的目标是尽量的让选择的区间达到最大化。 所以我们可以先对齐排序,因为输入是随机的。假设每个区间表示为(x,y)我们可以选择按照x排序所有区间,也可以选择按照y来排序所有区间。而不管选择哪一个来排序,其原理和本质都一样,都是为了方便操作,将其有序化。 我们这里选择按照y来排序,排序完后有y1 <= y2 <= y3....... 现在我们讨论x1 x2 .... 当x1 > x2时,区间被x2这个区间…

2013年4月5日 0条评论 2点热度 阅读全文

题目的大意是有F个农场,每个农场有N个牧场,M条双向路径,W个虫洞,虫洞是单向的,可以实现时间旅行,返回到以前某个时间。问从某个牧场出发,经过若干路径和虫洞,能否在没有离开出发地时回到出发地,见到自己。 其实就是一个用Bellman-Ford算法求负权环的问题,当图中存在负权环时,就能够在出发之前回到出发地,见着自己,将虫洞的权值加上负号,然后再用Bellman-Ford算法求解就可以了。 多说一句,应该看看POJ1860、POJ2240、POJ3259(本题)这三个题目,比较一下,加深对Bellman-Ford算…

2012年8月15日 0条评论 1点热度 阅读全文

Fence Repair Time Limit: 2000MS   Memory Limit: 65536K Total Submissions: 14281   Accepted: 4548 Description Farmer John wants to repair a small length of the fence around the pasture. He measures the fence and finds that he needs N (1 ≤ N ≤ 20,000) …

2012年4月16日 0条评论 1点热度 阅读全文