Cerinta completa
Greg wants to build a string, of length . Starting with an empty string, he can perform operations:
- Add a character to the end of for dollars.
- Copy any substring of , and then add it to the end of for dollars.
Calculate minimum amount of money Greg needs to build .
Input Format
The first line contains number of testcases .
The subsequent lines each describe a test case over lines:
The first contains space-separated integers, , , and , respectively.
The second contains (the string Greg wishes to build).
Constraints
- is composed of lowercase letters only.
Output Format
On a single line for each test case, print the minimum cost (as an integer) to build .
Sample Input
2
9 4 5
aabaacaba
9 8 9
bacbacacb
Sample Output
26
42
Explanation
Test Case 0:
“”; “”
Append ““; ““; cost is
Append ““; ““; cost is
Append ““; ““; cost is
Copy and append ““; ““; cost is
Append ““; ““; cost is
Copy and append ““; ““; cost is
Summing each cost, we get , so our output for Test Case 1 is .
Test Case 1:
“”; “”
Append ““; ““; cost is
Append ““; ““; cost is
Append ““; ““; cost is
Copy and append ““; ““; cost is
Copy and append ““; ““; cost is
Summing each cost, we get , so our output for Test Case 2 is .
Limbajul de programare folosit: cpp20
Cod:
#include <bits/stdc++.h>
using namespace std;
string ltrim(const string &);
string rtrim(const string &);
vector<string> split(const string &);
/*
* Complete the 'buildString' function below.
*
* The function is expected to return an INTEGER.
* The function accepts following parameters:
* 1. INTEGER a
* 2. INTEGER b
* 3. STRING s
*/
struct SparseMin {
vector<vector<int>> st;
vector<int> lg;
SparseMin() = default;
explicit SparseMin(const vector<int>& v) {
build(v);
}
void build(const vector<int>& v) {
int n = (int)v.size();
if (n == 0) {
st.clear();
lg = {0};
return;
}
lg.assign(n + 1, 0);
for (int i = 2; i <= n; ++i) lg[i] = lg[i / 2] + 1;
int K = lg[n] + 1;
st.assign(K, vector<int>(n));
st[0] = v;
for (int k = 1; k < K; ++k) {
int len = 1 << k;
int half = len >> 1;
for (int i = 0; i + len <= n; ++i) {
st[k][i] = min(st[k - 1][i], st[k - 1][i + half]);
}
}
}
int query(int l, int r) const {
if (l > r) return INT_MAX;
int len = r - l + 1;
int k = lg[len];
return min(st[k][l], st[k][r - (1 << k) + 1]);
}
};
struct SuffixArrayData {
string s;
int n = 0;
vector<int> sa;
vector<int> rk;
vector<int> lcp;
SparseMin stLcp;
SparseMin stSa;
explicit SuffixArrayData(const string& str) {
s = str;
n = (int)s.size();
buildSA();
buildLCP();
stLcp.build(lcp);
stSa.build(sa);
}
void buildSA() {
sa.resize(n);
rk.resize(n);
vector<int> tmp(n);
for (int i = 0; i < n; ++i) {
sa[i] = i;
rk[i] = s[i];
}
for (int k = 1;; k <<= 1) {
auto cmp = [&](int i, int j) {
if (rk[i] != rk[j]) return rk[i] < rk[j];
int ri = (i + k < n) ? rk[i + k] : -1;
int rj = (j + k < n) ? rk[j + k] : -1;
return ri < rj;
};
sort(sa.begin(), sa.end(), cmp);
tmp[sa[0]] = 0;
for (int i = 1; i < n; ++i) {
tmp[sa[i]] = tmp[sa[i - 1]] + (cmp(sa[i - 1], sa[i]) ? 1 : 0);
}
rk = tmp;
if (rk[sa[n - 1]] == n - 1) break;
}
vector<int> rankByPos(n);
for (int i = 0; i < n; ++i) rankByPos[sa[i]] = i;
rk.swap(rankByPos);
}
void buildLCP() {
if (n <= 1) {
lcp.clear();
return;
}
lcp.assign(n - 1, 0);
int h = 0;
for (int i = 0; i < n; ++i) {
int r = rk[i];
if (r == n - 1) {
h = 0;
continue;
}
int j = sa[r + 1];
while (i + h < n && j + h < n && s[i + h] == s[j + h]) ++h;
lcp[r] = h;
if (h > 0) --h;
}
}
// LCP length between suffixes starting at i and j.
int lcpSuffix(int i, int j) const {
if (i == j) return n - i;
int ri = rk[i], rj = rk[j];
if (ri > rj) swap(ri, rj);
return stLcp.query(ri, rj - 1);
}
bool hasEarlierOccurrence(int pos, int len) const {
if (len == 0) return true;
int r = rk[pos];
int left = r;
int lo = 0, hi = r;
while (lo < hi) {
int mid = (lo + hi) >> 1;
if (stLcp.query(mid, r - 1) >= len) hi = mid;
else lo = mid + 1;
}
left = lo;
int right = r;
lo = r;
hi = n - 1;
while (lo < hi) {
int mid = (lo + hi + 1) >> 1;
if (stLcp.query(r, mid - 1) >= len) lo = mid;
else hi = mid - 1;
}
right = lo;
int minStart = stSa.query(left, right);
return minStart <= pos - len;
}
int longestCopyFrom(int pos) const {
int lo = 0;
int hi = n - pos;
while (lo < hi) {
int mid = (lo + hi + 1) >> 1;
if (hasEarlierOccurrence(pos, mid)) lo = mid;
else hi = mid - 1;
}
return lo;
}
};
int buildString(int a, int b, string s) {
int n = (int)s.size();
SuffixArrayData sad(s);
vector<int> maxCopy(n, 0);
for (int i = 0; i < n; ++i) {
maxCopy[i] = sad.longestCopyFrom(i);
}
const long long INF = (1LL << 60);
vector<long long> dp(n + 1, INF);
dp[0] = 0;
for (int i = 0; i < n; ++i) {
if (dp[i] == INF) continue;
dp[i + 1] = min(dp[i + 1], dp[i] + a);
int len = maxCopy[i];
if (len > 0) {
dp[i + len] = min(dp[i + len], dp[i] + b);
}
}
return (int)dp[n];
}
int main()
{
ofstream fout(getenv("OUTPUT_PATH"));
string t_temp;
getline(cin, t_temp);
int t = stoi(ltrim(rtrim(t_temp)));
for (int t_itr = 0; t_itr < t; t_itr++) {
string first_multiple_input_temp;
getline(cin, first_multiple_input_temp);
vector<string> first_multiple_input = split(rtrim(first_multiple_input_temp));
int n = stoi(first_multiple_input[0]);
int a = stoi(first_multiple_input[1]);
int b = stoi(first_multiple_input[2]);
string s;
getline(cin, s);
int result = buildString(a, b, s);
fout << result << endl;
}
fout.close();
return 0;
}
string ltrim(const string &str) {
string s(str);
s.erase(
s.begin(),
find_if(s.begin(), s.end(), not1(ptr_fun<int, int>(isspace)))
);
return s;
}
string rtrim(const string &str) {
string s(str);
s.erase(
find_if(s.rbegin(), s.rend(), not1(ptr_fun<int, int>(isspace))).base(),
s.end()
);
return s;
}
vector<string> split(const string &str) {
vector<string> tokens;
string::size_type start = 0;
string::size_type end = 0;
while ((end = str.find(" ", start)) != string::npos) {
tokens.push_back(str.substr(start, end - start));
start = end + 1;
}
tokens.push_back(str.substr(start));
return tokens;
}
Scor obtinut: 1.0
Submission ID: 464636396
Link challenge: https://www.hackerrank.com/challenges/build-a-string/problem