B3829 [NICA #2] 字符串入门题题解

zheng_zx · 2023-10-30 14:01:22 · 题解

B3829 [NICA #2] 字符串入门题

题目传送门

题意

给定一个字符串 s，问能否把它划分成至少 k 个非空子串，且使每个子串都是其在原序列前的主串的子串。

分析

既然要把主串 s 分成 k 个子串，那么我们干脆直接让第一个子串最长，后面的每个子串长度都为 1。这样一来，我们只需先输出前 n-k+1 个字符，再遍历一遍后面的字符，如果没有出现过，那么直接输出 -1 即可通过此题。

AC code：

#include<bits/stdc++.h>
using namespace std;

int n, k, pos[10005], num = 0;
string s;

int main(){
    cin >> n >> k >> s;
    num = n - k + 1;
    for(int i = 0; i < num; ++i)
        pos[s[i]] = 1;//把出现过的字符标记为 1 
    for(int i = num; i < n; ++i)
        if(!pos[s[i]])//判断无解时的所有情况
        { 
            cout << -1 << endl;//未出现则输出 -1 
            return 0;//结束运行 
        }
    cout << k << endl;
    for(int i = 0; i <= n - k; ++i)
        cout << s[i];//输出主串 
    cout << endl; 
    for(int i = num; i < n; ++i)
        cout << s[i] << endl;//输出子串 
    return 0;//结束运行 
}

本蒟蒻第二次写题解，管理大大求过