首页 > 代码库 > 平方串

平方串

如果一个字符串由完全相同的两段字符串组成,我们称其为平方串,例如“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 }

 

平方串