文章
68
粉丝
691
获赞
26
访问
575.7k
依次遍历每个输入的字符串和目前已经形成的组别,如果与现有的一个组的所有字符串不互为前缀,那么将他加入该组,如果与某个组中的字符串冲突,那么如果该组中的前缀字符串短,则将其替换成较长的,如果他与所有组都冲突,那么另开一个组存它。
为什么选最长的?比如 如果一个组中现在是
acm yuou
现在输入一个
yuoufsdaf
显然yuou和yuoufsdaf是冲突的,如果我们保留yuou,那么遇到yuout这两个也是冲突的,但是如果我们将yuou换成yuoufsdaf,显然yuout也可以加入该组,贪心的选择长度较长的字符串替换短的,可以使得改组的字符串个数尽可能的多。也可能数据比较水哈,欢迎大佬指正
#define ll int
#define inf 0x3ffffff
#define vec vector<ll>
#define MAX 105
string a[MAX];
bool isT[MAX][MAX];
//检查a,b字符串是否一个是另一个的前缀
bool check(string a, string b) {
if (a.size() > b.size()) swap(a, b);
if (a == b.substr(0, a.size()))return true;
else return false;
}
int main() {
ll n;
while (cin >> n && n) {
cin.get();
for (int i = 1; i <= n; i++)getline(cin, a[i]);
for (int i = 1; i <= n; i++)
for (int j = i + 1; j <= n; j++)
isT[i][j] = check(a[i], a[j]);
vector<int> v[MAX]; ll cnt = 0, res = 0;//v存储的是字符串的编号
for (int i = 1; i <= n; i++) {//遍历所有字符串
ll sign = 0...
登录后发布评论
暂无评论,来抢沙发