题目链接: https://vjudge.net/contest/344930#problem/G
题目大意: 给你字符串, 如果他包含至少两个长度大于等于 3 的回文, 并且这些回文不能嵌套 (例如 aaa 嵌套在 aaaa,waw 嵌套在 awawa), 如果这个字符串这么牛逼的话, 就输出他.
题目思路: 其实这道题有一个贪心的思想在里面, 其实每次我们只需要去找长度为 3 和长度为 4 的回文串就好了. 这里的处理策略就是先处理长度为 3 的回文串, 再处理长度为 4 的回文串. 处理长度为 4 的回文串的时候, 要避免它的子串也是一个回文串.
- #include <stdio.h>
- #include <algorithm>
- #include <iostream>
- #include <stdlib.h>
- #include <string>
- #include <string.h>
- #include <math.h>
- #include <vector>
- #include <queue>
- #include <stack>
- #include <map>
- #include <set>
- #define INF 0x3f3f3f3f
- #define LL long long
- typedef unsigned long long ull;
- const int maxn = 1e5+10;
- char s[maxn];
- ull base = 131;
- ull mod = 1e9+7;
- ull p[maxn];
- ull h1[maxn],h2[maxn];
- ull q[maxn];
- ull get_hash(ull h[],int l,int r){
- return (h[r] - h[l-1]*p[r-l+1]);
- }
- bool check(char s[]) {
- std::set<ull> st;
- int ans = 0;
- int len = strlen(s+1);
- for (int i=2;i+1<=len;i++) {
- if (s[i-1] == s[i+1]) {
- ull temp = get_hash(h1,i-1,i+1);
- if (st.find(temp) == st.end()) {
- st.insert(temp);
- ans++;
- }
- }
- }
- for (int i=1;i+3<=len;i++) {
- if (s[i] == s[i+3] && s[i+1] == s[i+2]) {
- ull a = get_hash(h1,i,i+3);
- ull b = get_hash(h1,i+1,i+3);
- ull c = get_hash(h1,i,i+2);
- if (st.find(a) == st.end() && st.find(b) == st.end() && st.find(c) == st.end()) {
- ans++;
- st.insert(a);
- st.insert(b);
- st.insert(c);
- }
- }
- }
- return ans>= 2;
- }
- int main() {
- p[0] = 1;
- for (int i=1;i<maxn;i++) {
- p[i] = p[i-1] * base;
- }
- while (~scanf("%s",s+1)) {
- int len = strlen(s+1);
- for (int i=1;i<=len;i++) {
- h1[i] = h1[i-1] * base + s[i];
- }
- if (check(s)) {
- printf("%s\n",s+1);
- }
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3307974.html