首页 > 代码库 > 平方串
平方串
如果一个字符串由完全相同的两段字符串组成,我们称其为平方串,例如“aa”,"abab", 略去。
分析:输入长度为50,时间限制为1s,还要考虑判重,暴力枚举的复杂度为50*25*50=62500,在一秒的时间限制内完全可以,判重采用unordered_set来做,就可以了。
1 #include<bits/stdc++.h> 2 #define pb push_back 3 #define FOR(i, n) for (int i = 0; i < (int)n; ++i) 4 #define dbg(x) cout << #x << " at line " << __LINE__ << " is: " << x << endl 5 typedef long long ll; 6 using namespace std; 7 typedef pair<int, int> pii; 8 const int maxn = 1e3 + 10; 9 void solve() {10 string s;11 cin >> s;12 int n = s.size();13 unordered_set<string> se;14 for (int i = 0; i < n; i++) {15 for (int j = 2; i + j - 1 < n; j += 2) {16 int left = i, right = i + j / 2, len = j / 2;17 bool f = 1;18 for (int k = 0; k < len; k++) {19 if(s[left + k] != s[right + k]) {20 f = 0; break;21 }22 }23 if(f) {24 se.insert(s.substr(i, j));25 }26 }27 }28 cout << se.size() << endl;29 }30 int main() {31 freopen("test.in", "r", stdin);32 //freopen("test.out", "w", stdout);33 solve();34 return 0;35 }
平方串
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。