FZU 1409ファイル圧縮

 
 
ファイル圧縮
Time Limit:1 s
Memory limit:32 M
Acceepted Submit:302
Total Submit:1026
書類の圧縮率を上げることは常に人々の目標です.ここ数年、ファイルを並べ替えるだけで、圧縮していませんが、このようなアルゴリズムによって調整されたファイルを圧縮するアルゴリズムが提案されています.ほとんどの場合、もとより大きな圧縮率が得られます.このアルゴリズムは、具体的には、長さnの文字列Sに対して、まずこれに基づいてn文字列を構成し、i番目の文字列はSからi−1回左に循環シフトされた(例を参照).このn文字列を小さい文字から大きい文字に並べ替えます.2つの文字列の最初の文字が同じであれば、それらの相対的な位置は変わりません.続いて並べ替えられた文字列の最後の文字を新しい文字列S'に順次接続します.その長さはnであり、Sの文字の並び替えであることは明らかである.最後にS'とSの先頭文字を出力し、S'のシーケンス番号pです.例えば、

S = example

1、  n    ：
example
xamplee
ampleex
mpleexa
pleexam
leexamp
eexampl	
2、      ：
ampleex
example
eexampl
leexamp
mpleexa
pleexam
xamplee
3、  ：
S' = xelpame
p = 7

は英語の単語構造の特殊性のため、一部の文字が出現する頻度が高いため、同じ文字が中に並んでいる確率が高く、圧縮率が高くなります.このアルゴリズムは英語の単語の特性を利用しているが、実際には、ほとんどすべての種類のファイル圧縮に適していることが分かった.プログラムシミュレーションアルゴリズムの実行過程を作成してください.文字列S、出力S'とp.入出力フォーマット入力には2行が含まれます.第一の行為は整数nで、1<=n==10000で、Sの長さを表します.第二の行の文字列Sは、文字列はすべて小文字で構成され、他の文字はありません.2行、第1行S'、第2行整数pを出力します.入力例

7
example

出力例

xelpame
7

Original:FZUPC 2006
 
問題を解く:
       一つの方法は、multimapを用いて自動的に並べ替えられ、同じキーワードの値を格納することもできる.最初の要素を探すには、第一の要素はどの要素も違っています.ここではASCIIコードに数字を加えて、最後にどこにあるかを見てください.
       もう一つの方法は構造体で作ることができる.構造体には3つの変数(より少ないかもしれませんが)が格納されています.最初の文字、および最後の文字はもともと下付きです.タイトルは同じ文字で相対位置を変えないといけません.ここではsort関数は使えませんが、stable uuは使えます.SOrt()関数を並べ替えて、STLの各種の異なっている並べ替えについて、ここを見ることができます.
󑧙pragmawarning(disable:4786)荫include萶include啯啣include