青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

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 閱讀(1894) 評論(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

真的很贊  回復  更多評論   


青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            一区二区三区日韩| 亚洲美女在线国产| 亚洲韩国精品一区| 亚洲美女在线国产| 蜜桃久久av| 日韩一区二区精品视频| 欧美高清一区| 欧美成人免费在线| 99精品国产在热久久| 亚洲国产日韩在线一区模特| 美女性感视频久久久| 夜夜狂射影院欧美极品| 一本色道久久综合亚洲精品高清 | 亚洲自拍16p| 午夜视频在线观看一区二区三区 | 一区二区三区视频观看| 亚洲一区二区三区午夜| 黄网站色欧美视频| 亚洲美女av黄| 国产综合欧美在线看| 亚洲国产福利在线| 国产精品日日摸夜夜摸av| 欧美777四色影视在线| 欧美日韩精品一区二区在线播放| 午夜在线观看免费一区| 欧美a级在线| 欧美一区二区三区喷汁尤物| 久久资源av| 欧美在线综合| 欧美日韩国产精品一区二区亚洲| 久久精品一二三| 欧美欧美天天天天操| 久久久精品国产免费观看同学| 欧美激情国产日韩精品一区18| 欧美一区二区在线播放| 欧美激情网友自拍| 久热国产精品视频| 国产精品久久久久一区二区三区 | 香蕉成人久久| 欧美激情在线播放| 老色鬼精品视频在线观看播放| 欧美亚韩一区| 91久久国产综合久久| 狠狠久久婷婷| 小处雏高清一区二区三区| 一区二区三区国产精品| 久久亚洲国产精品日日av夜夜| 欧美一区二区三区另类| 欧美三级第一页| 亚洲电影在线播放| 亚洲高清成人| 久久国产精品一区二区三区四区| 午夜视频在线观看一区二区三区 | 欧美中文在线视频| 欧美一区午夜精品| 国产精品美女久久久久久2018| 最新国产成人在线观看| 亚洲日韩中文字幕在线播放| 久久久久久91香蕉国产| 久久久久久久波多野高潮日日| 国产精品福利网站| 一本色道久久精品| 亚洲尤物在线视频观看| 欧美日韩一区视频| 99re8这里有精品热视频免费| 99xxxx成人网| 欧美视频一区二区三区在线观看| 日韩午夜三级在线| 国产精品99久久久久久久vr| 欧美日韩国产一区精品一区| 亚洲精品视频一区| 中文一区二区| 国产精品视频免费一区| 午夜精品免费| 久久亚洲精品中文字幕冲田杏梨 | 国产精品免费一区二区三区在线观看 | 激情偷拍久久| 免费欧美在线| 亚洲精品国产精品乱码不99| 亚洲最新视频在线| 国产精品天天摸av网| 久久国产精品99久久久久久老狼 | 葵司免费一区二区三区四区五区| 激情文学综合丁香| 欧美精品性视频| 亚洲永久在线| 久久免费高清| 99国产精品视频免费观看一公开| 欧美日韩国产在线看| 亚洲免费伊人电影在线观看av| 久久精品在这里| 亚洲精品久久| 国产精品视频一区二区三区| 欧美一区二区三区四区在线| 免费日韩成人| 亚洲欧美精品在线| 在线视频观看日韩| 国产精品盗摄久久久| 欧美在线91| 99av国产精品欲麻豆| 久久婷婷激情| 亚洲一区综合| 亚洲第一天堂av| 国产精品入口福利| 欧美精品亚洲一区二区在线播放| 亚洲一区在线观看免费观看电影高清| 久久性色av| 亚洲欧美另类在线观看| 亚洲国产婷婷香蕉久久久久久99| 国产精品久久久久久久久久免费看 | 亚洲欧美日韩精品| 91久久夜色精品国产九色| 久久精品国产99国产精品| 亚洲人体大胆视频| 国内精品久久久久久久影视蜜臀| 欧美日韩高清在线观看| 久久久中精品2020中文| 亚洲欧美99| 一区二区三区欧美在线观看| 免费亚洲一区| 久久亚洲精品一区| 欧美一区二区三区婷婷月色| 一区二区三区免费网站| 亚洲国产一区二区三区高清| 国产亚洲精品久久久久婷婷瑜伽| 欧美日韩免费在线观看| 欧美大片第1页| 免费在线视频一区| 久久久久网址| 久久国产加勒比精品无码| 亚洲午夜精品福利| 亚洲性感激情| 亚洲午夜精品视频| 亚洲少妇自拍| 一本色道久久综合亚洲精品婷婷 | 欧美欧美天天天天操| 免费成人黄色片| 久久一区视频| 免费av成人在线| 农村妇女精品| 欧美国产第一页| 欧美极品影院| 欧美日韩免费看| 欧美视频中文字幕| 欧美香蕉视频| 国产精品制服诱惑| 国产亚洲观看| 在线观看久久av| 亚洲日本成人| 一区二区精品在线观看| 亚洲特级毛片| 欧美中文日韩| 久久一区二区视频| 欧美成人精品在线视频| 亚洲高清影视| 一区二区不卡在线视频 午夜欧美不卡在 | 亚洲欧美区自拍先锋| 欧美一区=区| 噜噜噜噜噜久久久久久91| 女生裸体视频一区二区三区| 亚洲福利专区| 一区二区三区视频在线| 午夜精品久久久久99热蜜桃导演| 午夜精品亚洲一区二区三区嫩草| 久久久久久国产精品mv| 欧美激情亚洲视频| 国产精品欧美久久| 一区精品久久| 日韩手机在线导航| 欧美专区福利在线| 欧美好吊妞视频| 在线午夜精品| 久久夜色精品亚洲噜噜国产mv| 欧美激情一区在线观看| 国产视频观看一区| 亚洲韩日在线| 午夜亚洲性色福利视频| 欧美肥婆在线| 亚洲欧美日韩视频二区| 欧美jjzz| 国产一区二区三区自拍| 在线视频精品一区| 免费成人av| 亚洲欧美中文日韩v在线观看| 老司机精品视频网站| 国产精品自拍小视频| 亚洲精品视频二区| 久久精品国产一区二区三区免费看| 亚洲高清精品中出| 欧美一区二区三区四区夜夜大片| 欧美激情日韩| 在线看片第一页欧美| 亚洲永久视频| 亚洲精品国产无天堂网2021| 久久动漫亚洲| 国产欧美日韩视频一区二区三区| 一区二区三区免费看| 欧美高清视频在线观看| 久久精品国产v日韩v亚洲| 国产精品激情av在线播放|