分析： 将字符串A，B连接，中间用一个符号隔开（这个符号的值要比字符串A，B里边的任何字符数组都要小），然后求sa和height。
求height的最大值，并且sa[i] 和sa[i-1] 要在不同的字符串中，后者的判断很仲要。
时间复杂度O（|A| + |B|）
#include "stdio.h"
#include "string.h"
#define maxn 200004
#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,j,n,ans=0;
scanf("%s",s);
j=strlen(s);
s[j]=1;
scanf("%s",s+j+1);
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);
for(i=2;i<=n;i++)
if(height[i]>ans)
if((j<sa[i-1] && j>sa[i])
|| (j>sa[i-1] && j<sa[i])) ans=height[i];
printf("%d\n",ans);
return 0;
}
posted @
2011-04-13 22:50 小阮 阅读(317) |
评论 (0) |
编辑 收藏
摘要: #include <iostream> using namespace std; template<int LIM,int MAX> class hp{ public: ...
阅读全文
posted @
2011-04-12 19:42 小阮 阅读(230) |
评论 (0) |
编辑 收藏
摘要: 题意：给定一个字符串，求至少出现 k 次的最长重复子串，这 k 个子串可以重叠。分析：先二分答案，然后将后缀分成若干组。 要判断的是有没有一个组的后缀个数不小于 k 。如果有，那么存在相同的子串满足条件，否则不存在。这个做法的时间复杂度为 O(nlogn) 。
#include <stdio.h>#define maxn 20003#define&nbs...
阅读全文
posted @
2011-04-09 23:45 小阮 阅读(273) |
评论 (0) |
编辑 收藏
摘要: 题意：求最长不重复子串分析：首先求后缀数组，height数组，由于是不重复的子串，所以不能只求height最大值。要把排序后的后缀分成若干组，其中每组的后缀之间的 height 值都不小于k。容易看出，有希望成为最长公共前缀不小于 k 的两个后缀一定在同一组。 然后对于每组后缀，只须判断每个后缀的 sa 值的最大值和最小值之差是否不小于k 。如果有一组满足，则说明存在，否则不存在。整个做法的时间复...
阅读全文
posted @
2011-03-30 22:44 小阮 阅读(275) |
评论 (0) |
编辑 收藏
摘要: 题意：n个字符组成长度为m的串，有一系列模式串pi，求不包含这些模式串的串有多少。分析：对这些模式串构建AC自动机。AC自动机其实就是trie树+失败指针，原理和KMP算法差不多。失败指针的建立可以采用BFS，对于每个节点，我们可以这样处理：设这个节点上的字母为C，沿着他父亲的失败指针走，直到走到一个节点，他的儿子中也有字母为C的节点。然后把当前节点的失败指针指向那个字目也为C的儿子。如果一直走到...
阅读全文
posted @
2011-03-22 22:58 小阮 阅读(562) |
评论 (1) |
编辑 收藏
题意：给定一个n*m的字符阵列中，查找给出字串匹配的开始坐标位置， 配置可以是从开始坐标向四周8个方向。
分析：对需要匹配的字串建立trie树，枚举字符阵列的每个位置，每个方向，进行查询。
#include <iostream>
using namespace std;
const int MAX = 90000;
const int M = 26, N = 1005, W=1005;
const int DX[] = { -1,-1, 0, 1, 1, 1, 0, -1 };
const int DY[] = { 0, 1, 1, 1, 0, -1, -1, -1 };
const char D[] = {'A','B','C','D','E','F','G','H'};
int sx,sy;
int n,m,w;
int index;
char puzzles[N][N], word[W];
int r[W][3];
struct Node{
int end;
struct Node* child[M];
Node(){
end=-1;
memset(child,NULL,sizeof(child));
}
};
Node tree;
Node *root = &tree;
void insert( char* s, int d){
Node *node = root;
while(*s){
if(index==20){
printf(" ");
}
if(node->child[*s-'A']==NULL){
node->child[*s-'A'] = new Node;
}
node=node->child[*s-'A'];
s++;
}
node->end = d;
}
void search(int x, int y, int d){
Node *node = root->child[puzzles[x][y]-'A'];
if(node==NULL)
return;
while(node){
if(node->end>-1){
r[node->end][0] = sx;
r[node->end][1] = sy;
r[node->end][2] = d;
}
x=x+DX[d];
y=y+DY[d];
if( x>=0 && x<n && y>=0 && y<m ){
node=node->child[puzzles[x][y]-'A'];
}else
break ;
}
return;
}
void solve(){
int i,j,k;
for(i=0;i<n;++i)
for(j=0;j<m;++j)
for(k=0;k<8;++k){
sx = i;
sy = j;
search(i,j,k);
}
}
int main(){
int i;
scanf("%d%d%d", &n, &m, &w);
for(i=0;i<n;++i){
scanf("%s", &puzzles[i]);
}
for(i=0;i<w;++i){
scanf("%s", &word[i]);
insert(&word[i],i);
}
solve();
for(i=0;i<w;++i)
printf("%d %d %c\n", r[i][0], r[i][1], D[r[i][2]]);
return 0;
}
posted @
2011-03-16 00:41 小阮 阅读(236) |
评论 (0) |
编辑 收藏题意：统计由d个不同字符组成的串中，长度为n的不同字串数目。
分析：Rabin Karp
Rabin-Karp 算法（以下简称为 RK 算法），是基于这样的思路：即把串看作是字符集长度进制的数，由数的比较得出字符串的比较结果。例如，给定字符集为∑ ={0,1,2,3,4,5,6,7,8,9} ，∑长度为 d=10 ，那么任何以∑为字符集的串都可看作 d （此处为 10 ）进制的数。
记模式串 P[0..n-1] 对应的数值为 P ， T[0..n-1] 所有长度为 m 的子串对应的数值为 ts ，设 P 和 T 都是基于字符集长度为 | ∑ |=d 的字符串。
那么， ts 即为 T[s..s+m] 对应的数值，这里 0<=s<=n-m-1 。
P = P[m]+d*(P[m-1]+d*(P[m-2]+..)))
同样 t0 也可类似求得。
最重要的是如何从 ts 求出 ts+1 。
ts+1 =T[s+m]+d*(ts +dm-1 *T[s])
注：此处是该算法的关键，即在常数时间内能够计算出下一个 m 长度的字串对应的数值。初看比较抽象，举个例子就比较明白了，设 x=12345 ，现在是已知长度为 3 的数值 234 ，现在要求 345 对应的数值，可以这样来得到： 345 = 5 + 10*(234-102 *2)
#include <iostream>
using namespace std;
const int MAX = 100000000;
bool hash[MAX];
char text[MAX];
int key[256],c[10000], ans;
int main(){
int i, n,d,len;
//freopen("input.txt","r", stdin);
scanf("%d%d", &n, &d);
scanf("%s", text);
len = strlen(text);
//init
c[0]=1;
for(i=1; i<10000; i++)
c[i] = c[i-1]*d;
int k=0;
for(i=0; i<len; ++i){
if(key[text[i]]==0)
key[text[i]]=k++;
if(k==d)
break;
}
//sovle
int h=0;
for(i=0; i<n; ++i)
h = h*d + key[text[i]];
hash[h]=true;
ans++;
for(i=0; i<len-n; ++i){
h = d*(h-c[n-1]*key[text[i]]) + key[text[i+n]];
if(!hash[h]){
hash[h]=true;
ans++;
}
}
printf("%d\n", ans);
return 0;
}
posted @
2011-03-16 00:08 小阮 阅读(303) |
评论 (0) |
编辑 收藏【问题分析】
二分图点权最大独立集，转化为最小割模型，从而用最大流解决。
【建模方法】
首先把棋盘黑白染色，使相邻格子颜色不同，所有黑色格子看做二分图X集合中顶点，白色格子看做Y集合顶点，建立附加源S汇T。
1、从S向X集合中每个顶点连接一条容量为格子中数值的有向边。
2、从Y集合中每个顶点向T连接一条容量为格子中数值的有向边。
3、相邻黑白格子Xi,Yj之间从Xi向Yj连接一条容量为无穷大的有向边。
求出网络最大流，要求的结果就是所有格子中数值之和减去最大流量。
【建模分析】
这是一个二分图最大点权独立集问题，就是找出图中一些点，使得这些点之间没有边相连，这些点的权值之和最大。独立集与覆盖集是互补的，求最大点权独立集可以转化为求最小点权覆盖集（最小点权支配集）。最小点权覆盖集问题可以转化为最小割问题解决。结论:最大点权独立集 = 所有点权 - 最小点权覆盖集 = 所有点权 - 最小割集 = 所有点权 - 网络最大流。
对于一个网络，除去冗余点（不存在一条ST路径经过的点），每个顶点都在一个从S到T的路径上。割的性质就是不存在从S到T的路径，简单割可以认为割边关联的非ST节点为割点，而在二分图网络流模型中每个点必关联到一个割点（否则一定还有增广路，当前割不成立），所以一个割集对应了一个覆盖集（支配集）。最小点权覆盖集就是最小简单割，求最小简单割的建模方法就是把XY集合之间的变容量设为无穷大，此时的最小割就是最小简单割了。
有关二分图最大点权独立集问题，更多讨论见《最小割模型在信息学竞赛中的应用》作者胡伯涛。
posted @
2011-03-14 23:20 小阮 阅读(1371) |
评论 (0) |
编辑 收藏【问题分析】
二分图多重匹配问题，用最大流解决。
【建模方法】
建立二分图，每个类别为X集合中的顶点，每个题为Y集合中的顶点，增设附加源S和汇T。
1、从S向每个Xi连接一条容量为该类别所需数量的有向边。
2、从每个Yi向T连接一条容量为1的有向边。
3、如果一个题i属于一个类别j，连接一条从Xj到Yi容量为1的有向边。
求网络最大流，如果最大流量等于所有类别所需之和，则存在解，否则无解。对于每个类别，从X集合对应点出发的所有满流边，指向的B集合中的顶点就是该类别的所选的题（一个可行解）。
【建模分析】
二分图多重匹配问题。X，Y集合之间的边容量全部是1，保证两个点只能匹配一次，源汇的连边限制了每个点匹配的个数。求出网络最大流，如果流量等于X集合所有点与S边容量之和，那么则说明X集合每个点都有完备的多重匹配。
posted @
2011-03-13 23:53 小阮 阅读(829) |
评论 (0) |
编辑 收藏
【1】用名字空间表示逻辑结构
【2】将每个非局部的名字放入某个名字空间里，除了main之外；
【3】名字空间的设计应该让你能很方便地使用它，而又不会意外地访问了其他的无关名字空间；
【4】避免对名字空间使用很短的名字；
【5】如果需要，通过名字空间别名取缓和长名字空间的影相；
【6】避免和你的名字空间的用户添加太大的记法负担；
【7】在定义名字空间成员时使用namespace::member的形式；
【8】只在转换时，或者在局部作用域里，才用using namespace ；
【9】利用异常去松弛“错误”处理代码和正常代码之间的联系；
【10】采用用户定义类型作为异常，不用内部类型；
【11】当局部控制结构足以应付问题时，不要用异常。
posted @
2011-03-12 23:47 小阮 阅读(208) |
评论 (0) |
编辑 收藏