亚洲免费av电影一区二区三区,日韩爱爱视频,51精品视频一区二区三区,91视频爱爱,日韩欧美在线播放视频,中文字幕少妇AV,亚洲电影中文字幕,久久久久亚洲av成人网址,久久综合视频网站,国产在线不卡免费播放

        ?

        倍增法之后綴數(shù)組解決重復(fù)子串的問題

        2016-11-17 02:37:52周波柳杰
        中國新通信 2016年17期
        關(guān)鍵詞:排序

        周波 柳杰

        【摘要】后綴數(shù)組是處理字符串的有力工具。利用后綴數(shù)組解決字符串問題,無論是在時(shí)間復(fù)雜度和空間復(fù)雜度上,都非常有優(yōu)勢,在信息學(xué)競賽中也是非常實(shí)用的一個(gè)工具。本文分兩部分,第一部分介紹倍增法構(gòu)造后綴數(shù)組,第二部分介紹簡潔高效代碼的實(shí)現(xiàn)與應(yīng)用。

        【關(guān)鍵字】字符串 后綴 后綴數(shù)組 名次數(shù)組 快速排序

        后綴數(shù)組的實(shí)現(xiàn),本節(jié)主要介紹后綴數(shù)組的倍增法實(shí)現(xiàn)。

        一、基本定義

        簡單的說,后綴數(shù)組是“排第幾的后綴串首字母在哪里?”,名次數(shù)組是“后綴串排第幾?”。容易看出,后綴數(shù)組和名次數(shù)組為互逆運(yùn)算。如圖1所示。

        設(shè)字符串的長度為n。為了方便比較大小,可以在字符串后面添加一個(gè)字符,這個(gè)字符沒有在前面的字符中出現(xiàn)過,而且比前面的字符都要小。在求出名次數(shù)組后,可以僅用0(1)的時(shí)間比較任意兩個(gè)后綴的大小。在求出后綴數(shù)組或名次數(shù)組中的其中一個(gè)以后,便可以用0㈤的時(shí)間求出另外一個(gè)。任意兩個(gè)后綴如果直接比較大小,最多需要比較字符n次,也就是說最遲在比較第n個(gè)字符時(shí)一定能分出“勝負(fù)”。

        二、倍增算法

        倍增算法的主要思路是:用倍增的方法對每個(gè)字符開始的長度為2k的子字符串進(jìn)行排序,求出排名,即rank值。k從0開始,每次加1,當(dāng)2k大于n以后,每個(gè)字符開始的長度為2k的子字符串便相當(dāng)于所有的后綴。并且這些子字符串都一定已經(jīng)比較出大小,即rank值中沒有相同的值,那么此時(shí)的rank值就是最后的結(jié)果。每一次排序都利用上次長度的字符串的rank值,那么長度為2k的字符串就可以用兩個(gè)長度為2k-1的字符串的排名作為關(guān)鍵字表示,然后進(jìn)行排序,便得出了長度為2k的字符串的rank值。以字符串“aabaaaab”為例,整個(gè)過程如圖2所示。其中x、y是表示長度為2k的字符串的兩個(gè)關(guān)鍵字。

        猜你喜歡
        排序
        排排序
        排序不等式
        作者簡介
        名家名作(2021年9期)2021-10-08 01:31:36
        作者簡介
        名家名作(2021年4期)2021-05-12 09:40:02
        恐怖排序
        律句填空排序題的備考策略
        節(jié)日排序
        刻舟求劍
        兒童繪本(2018年5期)2018-04-12 16:45:32
        作者簡介(按文章先后排序)
        名家名作(2017年2期)2017-08-30 01:34:24
        按特定規(guī)律排序
        兒童與健康(2012年1期)2012-04-12 00:00:00
        色狠狠色噜噜av天堂一区| 一本久久伊人热热精品中文| 凹凸世界视频a一二三| 国产区女主播在线观看| 日本在线看片免费人成视频1000 | 亚洲 日韩 激情 无码 中出| 亚洲欧洲精品无码av| 尤物视频一区二区| 玩弄极品少妇被弄到高潮| 亚洲一区二区三区中文字幕网| 人妻少妇乱子伦精品| 日韩AV不卡六区七区| 中文乱码字幕在线中文乱码 | 免费视频亚洲一区二区三区| 麻豆md0077饥渴少妇| 少妇被躁爽到高潮无码文 | 一区二区三区在线视频爽| 免费人成视频网站在线不卡| 无码少妇一区二区性色av| 无国产精品白浆免费视| 在线一区二区三区免费视频观看| av日韩一区二区三区四区| 久久99久久99精品中文字幕| 国产高潮精品久久AV无码| 日本加勒比一区二区在线观看| 日韩亚洲精品中文字幕在线观看| 男男性恋免费视频网站| 成人片在线看无码不卡| 中文字幕人乱码中文字幕乱码在线 | 国产免费a∨片在线软件| 18禁美女裸体网站无遮挡| 亚洲精品尤物av在线网站| 日韩少妇人妻中文视频| 麻豆精品久久久久久久99蜜桃 | 被欺辱的高贵人妻被中出| 99蜜桃在线观看免费视频| 欧美日韩精品久久久久| 国产国拍亚洲精品mv在线观看| 久久色悠悠亚洲综合网| 亚洲精品国产电影| 亚洲va中文字幕无码|