最近在看后缀数组,刚开始看完后,自己写个后缀数组的倍增算法都累死了(ps:lz太菜了),慢慢写了几道之后好多了。
poj 1743:
题目求最长不想交子字符串,
方法是二分长度k求上限,然后根据k把height数组分组,每组字符串间的公共长度大于=k,然后对于每个组,如果sa[i]的最大值和最小值相差大于k,那么就存在两个子字符串不相交,这个k就满足题意。
#include<cstring>
#include<cstdio>
int n;
int wa[20010],wb[20010],ws[20010],rank[20010],sa[20010],wv[20010],height[20010],r[20010];
int cmp(int *r,int a,int b......
阅读全文