admin管理员组文章数量:1615689
题意:
求N<=2000个串(L<=200)的最长公共子串,多解输出字典序最小的
分析:
直接O(2002∗2000∗匹配)暴力可以过,这题数据随机
用第一个串的所有个后缀去kmp匹配其他串,求的最小的匹配长度,复杂度可以降低到O(200∗2000∗200)
暴力代码:
//
// Created by TaoSama on 2015-10-30
// Copyright (c) 2015 TaoSama. All rights reserved.
//
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <string>
#include <set>
#include <vector>
using namespace std;
#define pr(x) cout << #x << " = " << x << " "
#define prln(x) cout << #x << " = " << x << endl
const int N = 1e5 + 10, INF = 0x3f3f3f3f, MOD = 1e9 + 7;
int n;
string s[4005];
int main() {
#ifdef LOCAL
freopen("C:\\Users\\TaoSama\\Desktop\\in.txt", "r", stdin);
// freopen("C:\\Users\\TaoSama\\Desktop\\out.txt","w",stdout);
#endif
ios_base::sync_with_stdio(0);
while(cin >> n && n) {
int minv = INF;
for(int i = 1; i <= n; ++i) {
cin >> s[i];
minv = min(minv, (int)s[i].size());
}
string ans;
for(int sz = minv; sz; --sz) {
for(int st = 0; st + sz - 1 < s[1].size(); ++st) {
bool ok = true;
string cur = s[1].substr(st, sz);
for(int i = 2; i <= n; ++i) {
if(s[i].find(cur) == string::npos) {
ok = false;
break;
}
}
if(!ok) continue;
if(!ans.size() || cur < ans) ans = cur;
}
if(ans.size()) break;
}
if(ans.size()) cout << ans << '\n';
else cout << "IDENTITY LOST\n";
}
return 0;
}
本文标签: 暴力hduCorporateKMPIDENTITY
版权声明:本文标题:HDU 2328 Corporate Identity (暴力 | kmp) 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://m.elefans.com/dianzi/1728725014a1170622.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论