# coreBugZJ

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

Problem 2012 AC's code

## 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.

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 ( 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 为大质数，

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 阅读(1739) 评论(9)  编辑 收藏 引用 所属分类: ACM

### Feedback

@sodaisinie

回复  更多评论

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

@maoyu

PS：这是我第一次写字符串 hash，以前字典树Trie用的比较多（对大量长字符串没辙 ^_^ ）  回复  更多评论

@maoyu