FZU 1409 檔案壓縮

檔案壓縮

Time Limit:1s

Memory limit:32M

Accepted Submit:302

Total Submit:1026

提高檔案的壓縮率一直是人們追求的目标。近幾年有人提出了這樣一種算法，它雖然隻是單純地對檔案進行重排，本身并不壓縮檔案，但是對經這種算法調整後的檔案進行壓縮，在大多數情況下都能獲得比原來更大的壓縮率。

該算法具體如下：對一個長度為n的字元串S，首先根據它構造n個字元串，其中第i個字元串由S向左循環移位i-1次得到（見示例）。然後把這n個字元串按照首字元從小到大排序。如果兩個字元串的首字元相同，則它們的相對位置不變。接着把排序後的字元串的尾字元依次連成一個新的字元串S'。它的長度仍為n，而且顯然是S中的字元的一種重排。最後輸出S'以及S的首字元在S'中的序号p。例如：

由于英語單詞構造的特殊性，某些字母出現的頻率很高，是以在 中相同的字母有很大幾率排在一起，進而提高 的壓縮率。雖然這種算法利用了英語單詞的特性，然而在實踐中，人們發現它幾乎适用于所有類型的檔案壓縮。

請你編寫一個程式模拟該算法的運作過程，輸入字元串S，輸出S'和p。

輸入輸出格式

輸入包含兩行。第一行為一整數n，1<=n<=10000，表示S的長度；第二行為字元串S，字元串全部由小寫字母組成，沒有其它字元。

輸出兩行，第一行為S'，第二行為整數p。

輸入樣例

輸出樣例

Original: FZUPC 2006

解題：

       一種方法可以使用multimap自動排序，還可以存儲相同關鍵字的值。要尋找第一個元素可以令第一個元素不同任何一個元素，這裡将它ASCII碼加上一個數字，最後在看下它在哪裡即可。

       另一種方法，可以用結構體來做。結構體裡面可以存儲三個變量（或許可以更少），首尾字元，還有尾字元本來的下标（這裡都是指排序後的）。題目要求相同首字元不改變相對位置，這裡不能使用sort函數，但是可以使用stable_sort()函數來排序，對于STL的各種不同排序，可以看這裡。

#pragma warning(disable:4786)

#include <iostream>

#include <string>

#include <map>

using namespace std;

int main()

{

int n,i,j;

string s;

multimap <char,char> words;

multimap <char,char>::iterator iter;

while (cin>>n)

cin>>s;

if (n==1)

cout<<s<<endl<<1<<endl;

continue;

}

words.insert(make_pair(s[0],s[n-1]));

words.insert(make_pair(s[1],s[0]+60));

for (i=2;i<n;i++)

words.insert(make_pair(s[i],s[i-1]));

for (iter=words.begin(),i=1;iter!=words.end();iter++,i++)

if (iter->second<97 || iter->second>122)

cout<<(char)(iter->second-60);

j=i;

else

cout<<iter->second;

cout<<endl<<j<<endl;

words.clear();j=0;

return 0;