随笔-141  评论-9  文章-3  trackbacks-0
 

分析: 将字符串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==2return 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 小阮 阅读(297) | 评论 (0)编辑 收藏
     摘要: #include <iostream> using namespace std; template<int LIM,int MAX> class hp{    public:      ...  阅读全文
posted @ 2011-04-12 19:42 小阮 阅读(216) | 评论 (0)编辑 收藏
     摘要: 题意:给定一个字符串,求至少出现 k 次的最长重复子串,这 k 个子串可以重叠。分析:先二分答案,然后将后缀分成若干组。 要判断的是有没有一个组的后缀个数不小于 k 。如果有,那么存在相同的子串满足条件,否则不存在。这个做法的时间复杂度为 O(nlogn) 。 #include <stdio.h>#define maxn 20003#define&nbs...  阅读全文
posted @ 2011-04-09 23:45 小阮 阅读(261) | 评论 (0)编辑 收藏
     摘要: 题意:求最长不重复子串分析:首先求后缀数组,height数组,由于是不重复的子串,所以不能只求height最大值。要把排序后的后缀分成若干组,其中每组的后缀之间的 height 值都不小于k。容易看出,有希望成为最长公共前缀不小于 k 的两个后缀一定在同一组。 然后对于每组后缀,只须判断每个后缀的 sa 值的最大值和最小值之差是否不小于k 。如果有一组满足,则说明存在,否则不存在。整个做法的时间复...  阅读全文
posted @ 2011-03-30 22:44 小阮 阅读(261) | 评论 (0)编辑 收藏
     摘要: 题意:n个字符组成长度为m的串,有一系列模式串pi,求不包含这些模式串的串有多少。分析:对这些模式串构建AC自动机。AC自动机其实就是trie树+失败指针,原理和KMP算法差不多。失败指针的建立可以采用BFS,对于每个节点,我们可以这样处理:设这个节点上的字母为C,沿着他父亲的失败指针走,直到走到一个节点,他的儿子中也有字母为C的节点。然后把当前节点的失败指针指向那个字目也为C的儿子。如果一直走到...  阅读全文
posted @ 2011-03-22 22:58 小阮 阅读(538) | 评论 (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<&& 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 小阮 阅读(218) | 评论 (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*+ 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 小阮 阅读(287) | 评论 (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 小阮 阅读(1317) | 评论 (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 小阮 阅读(808) | 评论 (0)编辑 收藏
【1】用名字空间表示逻辑结构
【2】将每个非局部的名字放入某个名字空间里,除了main之外;
【3】名字空间的设计应该让你能很方便地使用它,而又不会意外地访问了其他的无关名字空间;
【4】避免对名字空间使用很短的名字;
【5】如果需要,通过名字空间别名取缓和长名字空间的影相;
【6】避免和你的名字空间的用户添加太大的记法负担;
【7】在定义名字空间成员时使用namespace::member的形式;
【8】只在转换时,或者在局部作用域里,才用using namespace ;
【9】利用异常去松弛“错误”处理代码和正常代码之间的联系;
【10】采用用户定义类型作为异常,不用内部类型;
【11】当局部控制结构足以应付问题时,不要用异常。
posted @ 2011-03-12 23:47 小阮 阅读(199) | 评论 (0)编辑 收藏
仅列出标题
共14页: 1 2 3 4 5 6 7 8 9 Last