coreBugZJ

此 blog 已弃。

AC's code , FZU 2011年3月月赛之 C, FZU 2012

Problem 2012 AC's code

Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

AC is given two strings A and B, and then he wants to insert B into A. As we know, there are |A| + 1 possible ways to make the final string! For example, if A = “orz” and B = “p”, then AC may get four final strings: “porz”, “oprz”, “orpz”, “orzp”. However, these strings are not so beautiful, so AC sort them in lexicographic order, then he gets {“oprz”, “orpz”, “orzp”,”porz”}.

Now AC wants to know the k-th string in the sorted strings! For example, if AC wants to know the first string in the sorted strings, the answer is “oprz”, the second is “orpz”, the third is “orzp”, and the 4-th is “porz”.

Now you are given string A and B, and the number K, in this problem, AC guarantees that K is valid.

Input

The first line of the input data is an integer number T (T <= 1000), represent the number of test cases.

For each case, three lines follow.

The first line has one string indicates A. (Without any space in A)

The second line has one string indicates B. (Without any space in B)

The third line has one integer indicates K.

(1 <= |A|, |B| <= 10000, 1 <= K <= |A| + 1)

Output

For each test case, output a single line “Case idx:” where idx is the test case number starts from 1. Then one line output the k-th string in the sorted string.

Sample Input

4
orz
p
1
orz
p
2
orz
p
3
orz
p
4

Sample Output

Case 1:
oprz
Case 2:
orpz
Case 3:
orzp
Case 4:
porz



分析:
字符串 hash,求第 k 小元素。

字符串hash 函数为
hash ( s[ 0..n ] ) = ( s[0]*q^n + s[1]*q^(n-1) + ...... + s[n-1]*q^1 + s[n]*q^0 ) mod p,其中,p, q 为大质数,
适当预处理(见函数init )后,B 插入在 A 中任意位置所形成的字符串的任意前缀的hash 值都能 O(1) 计算出来(见函数hash)。

求第 k 小元素可以使用修改的快速排序(见函数sort),其中要注意使用随机,否则超时。复杂度 O(n)。

比较两个字符串大小时,只比较它们的最长公共前缀的后一个字符(见函数 cmp)。
而最长公共前缀通过二分其长度,用hash值判断是否相等,可以O(log(|A|+|B|) )得到(见函数 cmp)。

另一种做法是用后缀数组的。


我的代码:
  1#include <stdio.h>
  2#include <string.h>
  3#include <stdlib.h>
  4#include <time.h>
  5
  6typedef  long long  Lint;
  7
  8#define  PRIME  55566677
  9#define  HH     23456789
 10
 11#define  L  21009
 12
 13int la, lb, k;
 14char a[ L ], b[ L ], c[ L + L ];
 15Lint ha[ L ], hb[ L ], hh[ L ];
 16
 17void init() {
 18        int i;
 19        srand( time( 0 ) );
 20
 21        memset( ha, 0sizeof(ha) );
 22        ha[ 0 ] = a[ 0 ] % PRIME;
 23        for ( i = 1; a[ i ]; ++i ) {
 24                ha[ i ] = ( ha[ i - 1 ] * HH + a[ i ] ) % PRIME;
 25        }

 26        la = i;
 27
 28        memset( hb, 0sizeof(hb) );
 29        hb[ 0 ] = b[ 0 ] % PRIME;
 30        for ( i = 1; b[ i ]; ++i ) {
 31                hb[ i ] = ( hb[ i - 1 ] * HH + b[ i ] ) % PRIME;
 32        }

 33        lb = i;
 34
 35        hh[ 0 ] = 1;
 36        for ( i = 1; i < L; ++i ) {
 37                hh[ i ] = ( hh[ i -1 ] * HH ) % PRIME;
 38        }

 39}

 40
 41/*
 42insert b after a[ i ]
 43query hash of [0..j]
 44*/

 45Lint hash( int i, int j ) {
 46        if ( i < 0 ) {
 47                if ( j < lb ) {
 48                        return hb[ j ];
 49                }

 50                return ( hb[ lb-1 ] * hh[ j-lb+1 ] + ha[ j-lb ] ) % PRIME;
 51        }

 52        if ( j <= i ) {
 53                return ha[ j ];
 54        }

 55        if ( j <= i + lb ) {
 56                return ( ha[ i ] * hh[ j-i ] + hb[ j-i-1 ] ) % PRIME;
 57        }

 58        return ( ha[i]*hh[j-i] + hb[lb-1]*hh[j-i-lb] + (ha[j-lb]+PRIME-((ha[i]*hh[j-lb-i])%PRIME)) ) % PRIME;
 59}

 60
 61char getint i, int j ) {
 62        if ( i < 0 ) {
 63                if ( j < lb ) {
 64                        return b[ j ];
 65                }

 66                return a[ j-lb ];
 67        }

 68        if ( j <= i ) {
 69                return a[ j ];
 70        }

 71        if ( j <= i + lb ) {
 72                return b[ j-i-1 ];
 73        }

 74        return a[ j-lb ];
 75}

 76
 77int cmp( int i, int j ) {
 78        int low = 0, high = la+lb-1, mid, lcp=-1;
 79        while ( low <= high ) {
 80                mid = ( low + high ) / 2;
 81                if ( hash(i,mid)==hash(j,mid) ) {
 82                        low = mid + 1;
 83                        if ( lcp < mid ) {
 84                                lcp = mid;
 85                        }

 86                }

 87                else {
 88                        high = mid - 1;
 89                }

 90        }

 91        return get(i,lcp+1- get(j,lcp+1);
 92}

 93
 94int idx[ L ];
 95void sort( int le, int ri, int k ) {
 96        int i, j, x;
 97        if ( (le>=ri) || (k<1) ) {
 98                return;
 99        }

100        i = le + ( rand() % ( ri - le + 1 ) );
101        x = idx[ i ];
102        idx[ i ] = idx[ le ];
103        idx[ le ] = x;
104        i = le;
105        j = ri;
106        while ( i < j ) {
107                while ( (i<j) && (cmp(x,idx[j])<=0) ) {
108                        --j;
109                }

110                if ( i < j ) {
111                        idx[ i++ ] = idx[ j ];
112                }

113                while ( (i<j) && (cmp(idx[i],x)<=0) ) {
114                        ++i;
115                }

116                if ( i < j ) {
117                        idx[ j-- ] = idx[ i ];
118                }

119        }

120        idx[ i ] = x;
121        if ( i - le + 1 < k ) {
122                sort( i+1, ri, k-(i-le+1) );
123        }

124        else if ( i - le + 1 > k ) {
125                sort( le, i-1, k );
126        }

127}

128
129char* solve() {
130        int i, p;
131        char tmp;
132        for ( i = 0; i <= la; ++i ) {
133                idx[ i ] = i - 1;
134        }

135        sort( 0, la, k );
136        c[ 0 ] = 0;
137        p = idx[ k - 1 ];
138        tmp = a[ p + 1 ];
139        a[ p + 1 ] = 0;
140        strcat( c, a );
141        a[ p + 1 ] = tmp;
142        strcat( c, b );
143        strcat( c, a+p+1 );
144        return (char*)c;
145}

146
147int main() {
148        int td, cd = 0;
149        scanf( "%d"&td );
150        while ( td-- > 0 ) {
151                scanf( "%s%s%d", a, b, &k );
152                init();
153                printf( "Case %d:\n%s\n"++cd, solve() );
154        }

155        return 0;
156}

157


posted on 2011-03-21 21:12 coreBugZJ 阅读(1703) 评论(9)  编辑 收藏 引用 所属分类: ACM

Feedback

# re: AC's code , FZU 2011年3月月赛之 C, FZU 2012 2011-03-22 18:30 sodaisinie

代码无法打开啊  回复  更多评论   

# re: AC's code , FZU 2011年3月月赛之 C, FZU 2012 2011-03-22 18:52 coreBugZJ

@sodaisinie
原来是在ubuntu下用firefox编辑的。。。
已经win7下用IE重新编辑了  回复  更多评论   

# re: AC's code , FZU 2011年3月月赛之 C, FZU 2012 2011-03-22 21:17 sodaisinie

赞@coreBugZJ
  回复  更多评论   

# re: AC's code , FZU 2011年3月月赛之 C, FZU 2012 2011-03-23 16:26 maoyu

你好,请为什么这样的hash就可以保证没有重复值呢?万一出现两种添加方式经过hash后的值一样,怎么办呢?  回复  更多评论   

# re: AC's code , FZU 2011年3月月赛之 C, FZU 2012 2011-03-23 19:48 maoyu

还有一个疑问,这里用到的是大素数modP,我之前开了一个5位数的大素数,就WA了,然后把素数换成你的那两个,就AC了。那到底要多大呢?  回复  更多评论   

# re: AC's code , FZU 2011年3月月赛之 C, FZU 2012 2011-03-23 20:51 coreBugZJ

@maoyu
这个字符串 hash 从大空间映射到小空间,是有可能出现冲突的,只是输入空间虽大,需要区别的数据量不是很大,冲突的概率还是比较小的,素数开的大一些,降低冲突的概率。。。
PS:这是我第一次写字符串 hash,以前字典树Trie用的比较多(对大量长字符串没辙 ^_^ )  回复  更多评论   

# re: AC's code , FZU 2011年3月月赛之 C, FZU 2012 2011-03-24 17:45 maoyu

我看福大核武的题解,也是这么说。只是我个人觉得这题如果数据BT,需要两个不同的状态其hash值一定不同,我们能证明这种hash方法产生的每个状态hash值都不一样吗?  回复  更多评论   

# re: AC's code , FZU 2011年3月月赛之 C, FZU 2012 2011-03-24 17:56 coreBugZJ

@maoyu
我不能证明,比赛时我们就是卡在这一题和最后一题上,我是看了福大核武的题解过的。。。  回复  更多评论   

# re: AC's code , FZU 2011年3月月赛之 C, FZU 2012 2011-03-26 17:30 Dragon521

真的很赞  回复  更多评论   



只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理