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

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>
            亚洲国产成人精品久久久国产成人一区 | 精品成人在线| 欧美激情在线有限公司| 国产一区 二区 三区一级| 91久久线看在观草草青青| 韩国精品一区二区三区| 亚洲香蕉在线观看| 中文av字幕一区| 欧美国产欧美亚州国产日韩mv天天看完整| 久久国产精品久久精品国产| 欧美性猛交xxxx乱大交退制版 | 久久九九国产| 欧美在线视频观看| 国产精品揄拍一区二区| 亚洲午夜精品久久久久久浪潮 | 久久免费国产| 开元免费观看欧美电视剧网站| 国产乱码精品1区2区3区| 宅男噜噜噜66一区二区| 亚洲性感美女99在线| 欧美日韩成人一区| 99re热精品| 亚洲图片欧美一区| 欧美三级网址| 亚洲视频在线播放| 亚洲欧美日韩在线不卡| 久久国产色av| 国内久久婷婷综合| 欧美在线日韩| 欧美xx视频| 亚洲免费高清视频| 欧美日韩一二三四五区| 一区二区三区高清在线观看| 亚洲永久视频| 国产精品资源| 久久久999成人| 亚洲第一在线| 亚洲香蕉网站| 国产网站欧美日韩免费精品在线观看| 亚洲欧美日韩一区二区三区在线| 久久精品国产清高在天天线| 国产亚洲成人一区| 久久五月天婷婷| 亚洲精品久久久久| 欧美一级视频一区二区| 伊人久久亚洲热| 欧美激情一区二区三区不卡| 亚洲一二三区在线| 久久影视精品| 亚洲免费成人av| 国产美女精品视频| 久久天天躁狠狠躁夜夜爽蜜月| 欧美激情一区二区三区四区| 宅男精品视频| 国产一区二区三区免费不卡| 麻豆久久精品| 亚洲无吗在线| 欧美第一黄网免费网站| 亚洲欧美国产视频| 亚洲国产黄色片| 国产精品美女主播| 免费精品99久久国产综合精品| 一本色道久久综合亚洲精品不卡| 久久久久免费观看| 亚洲一区二区在线视频| 精品白丝av| 欧美日韩在线精品一区二区三区| 欧美专区福利在线| 亚洲大胆视频| 国产乱码精品一区二区三区不卡 | 一区二区三区在线免费视频| 欧美另类videos死尸| 久久超碰97人人做人人爱| 亚洲免费av网站| 免费在线视频一区| 欧美一区二区在线免费播放| 亚洲精品日韩在线观看| 黄色精品一区二区| 国产欧美日韩另类一区| 欧美日韩视频一区二区| 欧美成人免费小视频| 欧美在线观看www| 一本久久精品一区二区| 欧美大片在线观看| 久久精品二区三区| 亚洲一区二区在线免费观看视频| 亚洲国产小视频| 国产一区二区三区视频在线观看 | 美女主播精品视频一二三四| 午夜精品视频| 亚洲精品久久7777| 亚洲电影天堂av| 美女免费视频一区| 老司机一区二区三区| 久久久爽爽爽美女图片| 欧美在线视频一区二区三区| 亚洲欧美中日韩| 亚洲一区二区精品在线| 99re热这里只有精品视频| 亚洲激情av在线| 亚洲欧洲一区二区在线播放| 亚洲国产欧美一区二区三区久久| 黄色国产精品| 国产综合婷婷| 伊人成年综合电影网| 国产一区二区三区久久悠悠色av| 国产精品久久久久久av福利软件| 欧美日韩亚洲一区在线观看| 欧美日韩在线第一页| 国产精品成人久久久久| 国产精品稀缺呦系列在线| 国产精品区一区| 国产日韩精品一区二区| 国产亚洲综合在线| 狠狠久久婷婷| 亚洲国产91| 亚洲高清网站| 99在线热播精品免费| 亚洲一区成人| 久久成人一区二区| 欧美成人在线网站| 亚洲激精日韩激精欧美精品| 最新69国产成人精品视频免费 | 欧美大片免费观看| 亚洲人成亚洲人成在线观看| 亚洲作爱视频| 亚洲女性喷水在线观看一区| 久久精品国产2020观看福利| 麻豆精品在线视频| 欧美亚洲成人免费| 国内自拍一区| 欧美中文字幕在线播放| 久久亚洲精品一区二区| 欧美久久久久久| 国产精品永久免费观看| 亚洲盗摄视频| 亚洲小说欧美另类婷婷| 久久精品人人做人人综合| 欧美激情视频网站| 中文日韩在线视频| 久久久久久综合| 欧美日韩免费一区| 狠狠色狠狠色综合| 在线午夜精品自拍| 久久婷婷麻豆| 一区二区三区国产盗摄| 久久久久青草大香线综合精品| 欧美日韩激情网| 狠狠色伊人亚洲综合网站色| 亚洲最新合集| 老司机午夜精品视频| 宅男精品视频| 欧美大胆a视频| 国产一区二区日韩| 亚洲视频中文字幕| 你懂的视频一区二区| 亚洲午夜在线观看视频在线| 欧美大片第1页| 狠狠噜噜久久| 欧美一区三区二区在线观看| 亚洲欧洲在线免费| 久久夜色精品亚洲噜噜国产mv| 欧美午夜不卡影院在线观看完整版免费 | 亚洲欧洲日本在线| 久久久久久久久伊人| 一本色道久久综合| 欧美高清视频在线播放| 黄色成人在线免费| 久久国产精品黑丝| 亚洲视屏一区| 欧美日韩亚洲91| 亚洲精品小视频在线观看| 欧美jizz19hd性欧美| 亚洲欧美在线网| 国产精品久久久久aaaa| 亚洲午夜久久久久久久久电影院| 亚洲第一二三四五区| 久久久噜噜噜久久中文字幕色伊伊 | 夜色激情一区二区| 欧美激情一区| 久久综合狠狠综合久久综青草 | 欧美综合激情网| 国产精品最新自拍| 午夜视频在线观看一区二区| 日韩天堂av| 欧美日韩在线精品一区二区三区| 99视频一区二区三区| 亚洲欧洲另类| 久久尤物电影视频在线观看| 性欧美长视频| 国产专区综合网| 久久久久久97三级| 久久福利一区| 一区二区三区在线视频观看| 美女视频黄 久久| 美女国内精品自产拍在线播放| 亚洲第一搞黄网站| 欧美国产在线视频| 欧美激情精品久久久久| 一区二区三区日韩|