题意：
给你很多串，你需要找到这个串内有没有两个长度大于3的回文字符串，且要保证这两个回文字符串不相同，也不能完全覆盖，但可以重合一部分
题解：
首先判断回文的话可以通过马拉车算法（Manacher算法），如果在某个位置上回文长度大于3的话就要判断一下，如果串长为奇数，那么就取3，否则取4。
为什么呢？为了防止会完全覆盖
如果在i位置上面串长为奇数，那么我们只会取3，例如bab。此时你应该在下一个位置（即，i+1）去判断，而不能还在i位置找回文串（因为这个会和之前的有覆盖关系）
如果i+1位置回文串长度为奇数，例如babab（前面的bab是第i个位置的回文串），因为是奇数，我们只取3，所以只会取中间的3个，那么就不会和之前的有覆盖关系（其他情况你也可以自己去分析一下）
到这里还没有完，我们避免了完全覆盖，但是还要注意两个不同位置的回文串可能会相同，所以可以用哈希+map来判重
代码：
#include<stdio.h> #include<iostream> #include<algorithm> #include<string.h> #include<sstream> #include<map> using namespace std; typedef unsigned long long ull; const int maxn=110010; char s[maxn],str[maxn*2]; map<ull,int> mp; int Len[maxn*2],num; ull hash_[maxn],xp[maxn]; void init_() { xp[0]=1; for(int i=1;i<maxn;i++) xp[i]=xp[i-1]*13331; return ; } void init(int len) //这个是用来处理字符串的 { memset(str,0,sizeof(str)); int k=0; str[k++]='$'; for(int i=0;i<len;++i) str[k++]='#',str[k++]=s[i]; str[k++]='#'; num=k; } void manacher(int len) //求最长回文子串 { Len[0]=0; int sum=0; int id,mx=0; for(int i=1;i<len;++i) { if(i<mx) Len[i]=min(mx-i,Len[2*id-i]); else Len[i]=1; while(str[i-Len[i]]==str[i+Len[i]]) Len[i]++; if(Len[i]+i>mx) { mx=Len[i]+i; id=i; sum=max(sum,Len[i]); } } //return (sum-1); } void make_hash(char str[]) { int len=strlen(str); hash_[len]=0; for(int i=len-1;i>=0;i--) { hash_[i]=hash_[i+1]*13331+str[i]-'A'+1; } return ; } ull Get_hash(int i,int L) { return hash_[i]-hash_[i+L]*xp[L]; } int main() { int ans=0; init_(); while(scanf("%s",s)!=EOF) { mp.clear(); int len=strlen(s); init(len); make_hash(s); manacher(num);//manacher之后，Mp[i]-1为i位置的回文半径 int cnt=0; for(int i=0;i<2*len+2;i++) { if(Len[i]-1>=3) { if(Len[i]%2==1)//回文串为偶数，取长度四的回文串 { int st=(i-1)/2-2; int le=4; ull tmp=Get_hash(st,le); mp[tmp]++; } else//回文串为奇数，取长度三的回文串 { int st=i/2-2; int le=3; ull tmp=Get_hash(st,le); mp[tmp]++; } i++;//当前位置存在大于三的回文串，避免覆盖后移一位。 } } if(mp.size()>=2) printf("%s ",s); } return 0; }