arc155A
题目传送门：
ATC lg
题意：
给你一个长度为 n n n 的字符串 s s s，问你是否存在一个长度为 k k k 的字符串 s ′ s' s′ 使得 s + s ′ s + s' s+s′ 和 s ′ + s s' + s s′+s 都是回文串。
solution：
我们分讨一下。
-
k < n k < n k<n
对于这种情况我们发现只需 s s s 的后 n − k n - k n−k 个字符与前 n − k n - k n−k 个字符都是回文串且前 k k k 个字符与后 k k k 个字符相等即可。
-
⌊ k n ⌋ m o d 2 = 0 \left \lfloor \dfrac{k}{n} \right\rfloor \bmod 2 = 0 ⌊nk⌋mod2=0
我们只需要在两端各加上一些正着或倒着的 s s s，那最后就变成了 k k k 为 k m o d n k \bmod n kmodn 时的情况 1 1 1 了。
-
⌊ k n ⌋ m o d 2 = 1 \left \lfloor \dfrac{k}{n} \right\rfloor \bmod 2 = 1 ⌊nk⌋mod2=1
同样我们在一端各加上一个倒着的 s s s，就变成了 s s s 为 s + 倒着的 s s + \text{倒着的}s s+倒着的s， k k k 为 k − n k - n k−n 时的情况 2 2 2 了。
code: 时间复杂度 O ( n ) \mathcal{O}(n) O(n)
#include <bits/stdc++.h>
#define int ll
#define endl '\n'
#define il inline
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
string s;
int n, k;
il bool hw(string s) // 判回文
{for (int i = 0; i < s.size(); i++)if (s[i] != s[s.size() - i - 1])return 0;return 1;
}
signed main()
{ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);int T;cin >> T;while (T--){cin >> n >> k >> s;if ((k / n) & 1) // 情况三{k -= n;string t;for (int i = 0; i < s.size(); i++)t += s[s.size() - i - 1];s = t + s, n *= 2;}k %= n; // 情况二if (s.substr(0, k) == s.substr(n - k, k)) // 情况一cout << (hw(s.substr(k, n - k)) && hw(s.substr(0, n - k)) ? "Yes" : "No") << endl;elsecout << "No" << endl;}return 0;
}
