프로그램 명: suffix_array(open)

프로그램 명: suffix_array(open)

제한시간: 1 초

문자열 dovelet 이 주어질 때

0	1	2	3	4	5	6
d	o	v	e	l	e	t

이 문자열로 만들 수 있는 접미사는 7 개 이다.

• dovelet(0)
• ovelet(1)
• velet(2)
• elet(3)
• let(4)
• et(5)
• t(6)

이 접미사 배열(suffix array)을 정렬하면

• dovelet(0)
• elet(3)
• et(5)
• let(4)
• ovelet(1)
• t(6)
• velet(2)

입력

입력은 2000 이하의 문자열이 주어진다.

출력

정렬한 접미사 배열을 출력한다. 문자열과 수 사이에는 한 칸의 공백을 둔다.

입출력 예

입력

dovelet

출력

dovelet 0
elet 3
et 5
let 4
ovelet 1
t 6
velet 2

#include <iostream>

#include <string.h>

#include <algorithm>

#define M 2012

using namespace std;

char *stri;

struct form {

int num;

char *str;

int len;

bool operator<(const form &a) const {

for (int i = 0; i < strlen(stri); i++) {

if (str[i] != a.str[i])

return str[i] < a.str[i];

}

return true;

}

} arr[M];

int main() {

int i, j;

stri = new char[M];

cin >> stri;

for (i = 0; i < strlen(stri); i++) {

arr[i].num = i;

arr[i].str = stri+i;

arr[i].len = strlen(stri+i);

}

sort(arr, arr+strlen(stri));

for (i = 0; i < strlen(stri); i++)

cout << arr[i].str << " " << arr[i].num << endl;

return 0;

}

#include <string>

#include <algorithm>

#include <iostream>

#include <sstream>

#define M 2010

using namespace std;

int len;

struct form {

string str;

int num;

bool operator<(const form &a) const {

for (int i = 0; i < len; i++) {

if (str[i] != a.str[i])

return str[i] < a.str[i];

}

return true;

}

}arr[M];

int main() {

string cstr;

int i;

cin >> cstr;

for (i = 0; i < cstr.length(); i++) {

arr[i].num = i;

arr[i].str = cstr.begin()+i;

}

len = cstr.length();

sort(arr, arr+cstr.length());

for (i = 0; i < cstr.length(); i++)

cout << arr[i].str << " " << arr[i].num << endl;

return 0;

}