21W38-최적화 - 01 문자열 탐색

[moodmine]

https://swexpertacademy.com/main/learn/course/subjectDetail.do?courseId=AVuPDYSqAAbw5UW6&subjectId=AV5KmPTqDbUDFAXc#

[murry2018]

일단 naive 풀이입니다.

SWEA 1256. K번째 접미어

#include <cstdio>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

vector<string> allSuffix(const string &s) {
  vector<string> suff;
  string::const_iterator iter = s.cbegin();
  string::const_iterator send = s.cend();
  while (iter != send) {
    suff.emplace_back(iter, send);
    ++iter;
  }
  return suff;
}

string findKSuffix(vector<string> &suff, int k) {
  sort(suff.begin(), suff.end());
  return suff[k];
}

int numberOfSuffix(const string &s) {
  return s.length();
}

char buf[401];
int main() {
  int T;
  scanf("%d", &T);
  for (int t = 1; t <= T; t++) {
    int k;
    scanf("%d", &k);
    scanf("%s", buf);
    string s(buf);
    string res = "none";
    vector<string> suff;
    if (k <= numberOfSuffix(s)) {
      suff = allSuffix(s);
      res = findKSuffix(suff, k-1);
    }
    printf("#%d %s\n", t, res.c_str());
  }
}

SWEA 1257. K번째 문자열

#include <cstdio>
#include <vector>
#include <string>
#include <set>
#include <algorithm>
#include <iterator>
#include <cmath>

using namespace std;

vector<string> allSuffix(string &s) {
  vector<string> suffs; // RVO
  string::iterator iter = s.begin();
  string::iterator send = s.end();
  while (iter != send) {
    suffs.emplace_back(iter, send);
    ++iter;
  }
  return suffs;
}

set<string> substringsFromSuffices(vector<string> &suff) {
  set<string> subs;
  for (string &s : suff) {
    string::iterator iter = s.begin();
    string::iterator send = s.end();
    while (iter != send) {
      subs.emplace(iter, send);
      --send;
    }
  }
  return subs;
}

string kthSubstring(set<string> &subs, int k) {
  set<string>::iterator iter = subs.begin();
  advance(iter, k);
  return *iter;
}

int numberOfSubstrings(string &s) {
  return (int)pow(2, s.length())-1;
}

char buf[401];
int main() {
  int T;
  scanf("%d", &T);
  for (int t = 1; t <= T; t++) {
    int k;
    scanf("%d", &k);
    scanf("%s", buf);
    string s(buf);
    string res="none";
    if (k <= numberOfSubstrings(s)) {
      vector<string> suff = allSuffix(s);
      set<string> subs = substringsFromSuffices(suff);
      if (k <= subs.size())
        res = kthSubstring(subs, k-1);
    }
    printf("#%d %s\n", t, res.c_str());
  }
}