2011年6月30日

题意: 给定一个字符串, 求不相同的子串的个数.

分析:每个子串其实都是一个后缀的前缀, 原题等价于求: 所有后缀之间不相等前缀个数.

所有后缀按照 suffix(sa[1]), suffix(sa[2]), suffix(sa[3]), ... suffix(sa[n])排序,

每新加入一个后缀suffix(sa[k]), 就增加 n - sa[k] + 1 个前缀, 这些前缀中, 又有height[k]个与前一个后缀相同.

所有只是增加个 n-sa[k]+1-height[k];

整理下求和公示.

#include <stdio>
#include <cstring>

using namespace std;

const int  maxn = 1003

#define F(x) ((x)/3+((x)%3==1?0:tb))
#define G(x) ((x)<tb?(x)*3+1:((x)-tb)*3+2)

int wa[maxn],wb[maxn],wv[maxn],ws[maxn];

int c0(int *r,int a,int b){
    return r[a]==r[b]&&r[a+1]==r[b+1]&&r[a+2]==r[b+2];
}

int c12(int k,int *r,int a,int b){
    if(k==2) 
        return r[a]<r[b]||r[a]==r[b]&&c12(1,r,a+1,b+1);
    else 
        return r[a]<r[b]||r[a]==r[b]&&wv[a+1]<wv[b+1];
}

void sort(int *r,int *a,int *b,int n,int m){
     int i;
     for(i=0;i<n;i++) wv[i]=r[a[i]];
     for(i=0;i<m;i++) ws[i]=0;
     for(i=0;i<n;i++) ws[wv[i]]++;
     for(i=1;i<m;i++) ws[i]+=ws[i-1];
     for(i=n-1;i>=0;i--) b[--ws[wv[i]]]=a[i];
     return;
}

void dc3(int *r,int *sa,int n,int m){
     int i,j,*rn=r+n,*san=sa+n,ta=0,tb=(n+1)/3,tbc=0,p;
     r[n]=r[n+1]=0;
     for(i=0;i<n;i++) if(i%3!=0) wa[tbc++]=i;
     sort(r+2,wa,wb,tbc,m);
     sort(r+1,wb,wa,tbc,m);
     sort(r,wa,wb,tbc,m);
     for(p=1,rn[F(wb[0])]=0,i=1;i<tbc;i++)
     rn[F(wb[i])]=c0(r,wb[i-1],wb[i])?p-1:p++;
     if(p<tbc) dc3(rn,san,tbc,p);
     else for(i=0;i<tbc;i++) san[rn[i]]=i;
     for(i=0;i<tbc;i++) if(san[i]<tb) wb[ta++]=san[i]*3;
     if(n%3==1) wb[ta++]=n-1;
     sort(r,wb,wa,ta,m);
     for(i=0;i<tbc;i++) wv[wb[i]=G(san[i])]=i;
     for(i=0,j=0,p=0;i<ta && j<tbc;p++)
     sa[p]=c12(wb[j]%3,r,wa[i],wb[j])?wa[i++]:wb[j++];
     for(;i<ta;p++) sa[p]=wa[i++];
     for(;j<tbc;p++) sa[p]=wb[j++];
     return;
}

int rank[maxn],height[maxn];

void calheight(int *r,int *sa,int n){
     int i,j,k=0;
     for(i=1;i<=n;i++) rank[sa[i]]=i;
     for(i=0;i<n;height[rank[i++]]=k)
     for(k?k--:0,j=sa[rank[i]-1];r[i+k]==r[j+k];k++);
     return;
}

char s[maxn];
int r[maxn*3],sa[maxn*3];

int main(){
    int i,n,t,ans;
    scanf("%d",&t);
    while(t-->0){
      scanf("%s",s);
      n=strlen(s);
      for(i=0;i<n;i++) r[i]=s[i];
      r[n]=0;
      dc3(r,sa,n+1,128);
      calheight(r,sa,n);
      ans=n*(n+1)/2;
      for(i=1;i<=n;i++) ans-=height[i];
      printf("%d\n",ans);
    }
    return 0;
}

  2011年5月3日

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
 
using namespace std;
 
const int MAXN=1001;
 
class UFS{
    public:
    int F[MAXN];
    tUFS(){
        for (int i=1;i<MAXN;i++)F[i]=-i;
    }
    int findroot(int a){
        int r=a,t;
        while (F[r]>0) r=F[r];
        while (F[a]>0) {t=F[a];F[a]=r;a=t;}
        return r;
    }
    void Union(int a,int b){
        F[findroot(a)]=findroot(b);
    }
    bool Judge(int a,int b){
        return F[findroot(a)]==F[findroot(b)];
    }
    int getroot(int a){
        return -F[findroot(a)];
    }
};

[次短路径]

次短路径可以看作是k短路径问题的一种特殊情况，求k短路径有Yen算法等较为复杂的方法，对于次短路径，可以有更为简易的方法。下面介绍一种求两个顶点之间次短路径的解法。

我们要对一个有向赋权图(无向图每条边可以看作两条相反的有向边)的顶点S到T之间求次短路径，首先应求出S的单源最短路径。遍历有向图，标记出可以在最短路径上的边，加入集合K。然后枚举删除集合K中每条边，求从S到T的最短路径，记录每次求出的路径长度值，其最小值就是次短路径的长度。

在这里我们以为次短路径长度可以等于最短路径长度，如果想等，也可以看作是从S到T有不止一条最短路径。如果我们规定求从S到T大于最短路径长度的次短路径，则答案就是每次删边后大于原最短路径的S到T的最短路径长度的最小值。

用Dijkstra+堆求单源最短路径，则每次求最短路径时间复杂度为O(N*log(N+M) + M)，所以总的时间复杂度为O(N*M*log(N+M) + M^2)。该估计是较为悲观的，因为一般来说，在最短路径上的边的条数要远远小于M，所以实际效果要比预想的好。

[次小生成树]

类比上述次短路径求法，很容易想到一个“枚举删除最小生成树上的每条边，再求最小生成树”的直观解法。如果用Prim+堆，每次最小生成树时间复杂度为O(N*log(N+M) + M)，枚举删除有O(N)条边，时间复杂度就是O(N^2*log(N+M) + N*M)，当图很稠密时，接近O(N^3)。这种方法简易直观，但我们有一个更简单，而且效率更高的O(N^2+M)的解法，下面介绍这种方法。

首先求出原图最小生成树，记录权值之和为MinST。枚举添加每条不在最小生成树上的边(u,v)，加上以后一定会形成一个环。找到环上权值第二大的边(即除了(u,v)以外的权值最大的边)，把它删掉，计算当前生成树的权值之和。取所有枚举修改的生成树权值之和的最小值，就是次小生成树。

具体实现时，更简单的方法是从每个节点i遍历整个最小生成树，定义F[j]为从i到j的路径上最大边的权值。遍历图求出F[j]的值，然后对于添加每条不在最小生成树中的边(i,j)，新的生成树权值之和就是MinST + w(i,j) – F[j]，记录其最小值，则为次小生成树。

该算法的时间复杂度为O(N^2 + M)。由于只用求一次最小生成树，可以用最简单的Prim，时间复杂度为O(N^2)。算法的瓶颈不在求最小生成树，而在O(N^2+M)的枚举加边修改，所以用更好的最小生成树算法是没有必要的。

[次短路径与次小生成树的例题]

HAOI 2005 路由选择问题
直接求次短路径。

pku 3255 Roadblocks
稍微特殊的次短路径，允许边重复走。

Ural 1416 Confidential
求次小生成树的问题、

pku 1679 The Unique MST
判断最小生成树是否唯一。


http://www.byvoid.com/blog/2-sp-mst/

  2011年4月21日

1、首先需要一个内存池，目的在于：
·减少频繁的分配和释放，提高性能的同时，还能避免内存碎片的问题；
·能够存储变长的数据，不要很傻瓜地只能预分配一个最大长度；
·基于SLAB算法实现内存池是一个好的思路：分配不同大小的多个块，请求时返回大于请求长度的最小块即可，对于容器而言，处理固定块的分配和回收，相当容易实现。当然，还要记得需要设计成线程安全的，自旋锁比较好，使用读写自旋锁就更好了。
·分配内容的增长管理是一个问题，比如第一次需要1KB空间，随着数据源源不断的写入，第二次就需要4KB空间了。扩充空间容易实现，可是扩充的时候必然 涉及数据拷贝。甚至，扩充的需求很大，上百兆的数据，这样就不好办了。暂时没更好的想法，可以像STL一样，指数级增长的分配策略，拷贝数据虽不可避免， 但是起码重分配的几率越来越小了。
·上面提到的，如果是上百兆的数据扩展需要，采用内存映射文件来管理是一个好的办法：映射文件后，虽然占了很大的虚拟内存，但是物理内存仅在写入的时候才会被分配，加上madvice()来加上顺序写的优化建议后，物理内存的消耗也会变小。
·用string或者vector去管理内存并不明智，虽然很简单，但服务器软件开发中不适合使用STL，特别是对稳定性和性能要求很高的情况下。

2、第二个需要考虑的是对象池，与内存池类似：
·减少对象的分配和释放。其实C++对象也就是struct，把构造和析构脱离出来手动初始化和清理，保持对同一个缓冲区的循环利用，也就不难了。
·可以设计为一个对象池只能存放一种对象，则对象池的实现实际就是固定内存块的池化管理，非常简单。毕竟，对象的数量非常有限。

3、第三个需要的是队列：
·如果可以预料到极限的处理能力，采用固定大小的环形队列来作为缓冲区是比较不错的。一个生产者一个消费者是常见的应用场景，环形队列有其经典的“锁无关”算法，在一个线程读一个线程写的场景下，实现简单，性能还高，还不涉及资源的分配和释放。好啊，实在是好！
·涉及多个生产者消费者的时候，tbb::concurent_queue是不错的选择，线程安全，并发性也好，就是不知道资源的分配释放是否也管理得足够好。

4、第四个需要的是映射表，或者说hash表：
·因为epoll是事件触发的，而一系列的流程可能是分散在多个事件中的，因此，必须保留下中间状态，使得下一个事件触发的时候，能够接着上次处理的位置继续处理。要简单的话，STL的hash_map还行，不过得自己处理锁的问题，多线程环境下使用起来很麻烦。
·多线程环境下的hash表，最好的还是tbb::concurent_hash_map。

5、核心的线程是事件线程：
·事件线程是调用epoll_wait()等待事件的线程。例子代码里面，一个线程干了所有的事情，而需要开发一个高性能的服务器的时候，事件线程应该专注于事件本身的处理，将触发事件的socket句柄放到对应的处理队列中去，由具体的处理线程负责具体的工作。

6、accept()单独一个线程：
·服务端的socket句柄（就是调用bind()和listen()的这个）最好在单独的一个线程里面做accept()，阻塞还是非阻塞都无所谓，相比整个服务器的通讯，用户接入的动作只是很小一部分。而且，accept()不放在事件线程的循环里面，减少了判断。

7、接收线程单独一个：
·接收线程从发生EPOLLIN事件的队列中取出socket句柄，然后在这个句柄上调用recv接收数据，直到缓冲区没有数据为止。接收到的数据写入以socket为键的hash表中，hash表中有一个自增长的缓冲区，保存了客户端发过来的数据。
·这样的处理方式适合于客户端发来的数据很小的应用，比如HTTP服务器之类；假设是文件上传的服务器，则接受线程会一直处理某个连接的海量数据，其他客户端的数据处理产生了饥饿。所以，如果是文件上传服务器一类的场景，就不能这样设计。

8、发送线程单独一个：
·发送线程从发送队列获取需要发送数据的SOCKET句柄，在这些句柄上调用send()将数据发到客户端。队列中指保存了SOCKET句柄，具体的信息 还需要通过socket句柄在hash表中查找，定位到具体的对象。如同上面所讲，客户端信息的对象不但有一个变长的接收数据缓冲区，还有一个变长的发送 数据缓冲区。具体的工作线程发送数据的时候并不直接调用send()函数，而是将数据写到发送数据缓冲区，然后把SOCKET句柄放到发送线程队列。
·SOCKET句柄放到发送线程队列的另一种情况是：事件线程中发生了EPOLLOUT事件，说明TCP的发送缓冲区又有了可用的空间，这个时候可以把SOCKET句柄放到发送线程队列，一边触发send()的调用；
·需要注意的是：发送线程发送大量数据的时候，当频繁调用send()直到TCP的发送缓冲区满后，便无法再发送了。这个时候如果循环等待，则其他用户的 发送工作受到影响；如果不继续发送，则EPOLL的ET模式可能不会再产生事件。解决这个问题的办法是在发送线程内再建立队列，或者在用户信息对象上设置 标志，等到线程空闲的时候，再去继续发送这些未发送完成的数据。

9、需要一个定时器线程：
·一位将epoll使用的高手说道：“单纯靠epoll来管理描述符不泄露几乎是不可能的。完全解决方案很简单，就是对每个fd设置超时时间，如果超过timeout的时间，这个fd没有活跃过，就close掉”。
·所以，定时器线程定期轮训整个hash表，检查socket是否在规定的时间内未活动。未活动的SOCKET认为是超时，然后服务器主动关闭句柄，回收资源。

10、多个工作线程：
·工作线程由接收线程去触发：每次接收线程收到数据后，将有数据的SOCKET句柄放入一个工作队列中；工作线程再从工作队列获取SOCKET句柄，查询hash表，定位到用户信息对象，处理业务逻辑。
·工作线程如果需要发送数据，先把数据写入用户信息对象的发送缓冲区，然后把SOCKET句柄放到发送线程队列中去。
·对于任务队列，接收线程是生产者，多个工作线程是消费者；对于发送线程队列，多个工作线程是生产者，发送线程是消费者。在这里需要注意锁的问题，如果采用tbb::concurrent_queue，会轻松很多。

11、仅仅只用scoket句柄作为hash表的键，并不够：
·假设这样一种情况：事件线程刚把某SOCKET因发生EPOLLIN事件放入了接收队列，可是随即客户端异常断开了，事件线程又因为EPOLLERR事 件删除了hash表中的这一项。假设接收队列很长，发生异常的SOCKET还在队列中，等到接收线程处理到这个SOCKET的时候，并不能通过 SOCKET句柄索引到hash表中的对象。
·索引不到的情况也好处理，难点就在于，这个SOCKET句柄立即被另一个客户端使用了，接入线程为这个SCOKET建立了hash表中的某个对象。此时，句柄相同的两个SOCKET，其实已经是不同的两个客户端了。极端情况下，这种情况是可能发生的。
·解决的办法是，使用socket fd + sequence为hash表的键，sequence由接入线程在每次accept()后将一个整型值累加而得到。这样，就算SOCKET句柄被重用，也不会发生问题了。

12、监控，需要考虑：
·框架中最容易出问题的是工作线程：工作线程的处理速度太慢，就会使得各个队列暴涨，最终导致服务器崩溃。因此必须要限制每个队列允许的最大大小，且需要监视每个工作线程的处理时间，超过这个时间就应该采用某个办法结束掉工作线程。