Welcome, Guest! Sign Up RSS

Clever Space

Friday, 11.22.2024
Main » 2013 » October » 09
RK是好东西啊

Rabin-Karp算法在字符串匹配中其实也不算是很常用，但它的实用性还是不错的，除非你的运气特别差，最坏情况下可能会需要O((n-m)*m)的运行时间(关于n,m的意义请看上篇）。平均情况下，还是比较好的。

朴素的字符串匹配算法为什么慢？ 因为它太健忘了，前一次匹配的信息其实可以有部分可以应用到后一次匹配中的，而朴素的字符串匹配算法只是简单的把这个信息扔掉，从头再来，因此，浪费了时间。好好的利用这些信息，自然可以提高运行速度。

这个算法不是那么容易说清楚，我举一个例子说下（看算法导论看到的例子）。

我们用E来表示字母表的字母个数，这个例子字母表如下:{0,1,2,3,4,5,6,7,8,9}，那么E就是10，如果采用小写英文字母来做字母表，那么E就是26，类此。

由于完成两个 ... Read more »

Views: 383 | Added by: dhy0077 | Date: 10.09.2013

「Poetize10」封印一击

水题

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<vector>
#include<set>
#include<map>
#include<string>
#include<algorithm>
#define FOR(i,a,b) for(i=(a);i<=(b);i++)
#define ROF(i,a,b) for(i=(a);i>=(b);i--)
#define pb push_back
#define mp make_pair
#define N 500010
using namespace std;
typedef long long LL;
typedef long double LD;
struct node{LL d;int type;};
int cmp(node a,node b)
{
  if (a.d<b.d) return 1;
  if (a.d>b.d) return 0;
  return a.type>b.type;
}
node b[N];
int n,i,len;
LL tot=0,L,R;
int main()
{
  ios::sync_with_stdio(fa ... Read more »
Views: 245 | Added by: dhy0077 | Date: 10.09.2013

学校门口的滔天巨浪

好吧，无语了

明天（10.10）因为台风竟然又可休假

a long vacation


Views: 329 | Added by: dhy0077 | Date: 10.09.2013