字符串算法应用

S+字符串算法应用 A. 大厨的特色菜 这题直接分类讨论+暴力即可。 首先，当字符串长度小于 2 时，是肯定不满足条件的。 当字符串长度是偶数时，直接判断字符串前半段与后半段是否相等。 如果字符串长度是奇数，那么就枚举删除哪一个字符，再按照长度为偶数是的判断方法来判断即可。 #include using namespace std; bool check(string s){ if(s.substr(0,s.size()/2)==s.substr(s.size()/2,s.size()/2)) return 1; return 0; } int main(){ int n; cin>>n; while(n--){ string s; cin>>s; int a=s.size(); if(a `#include using namespace std; bool check(string s){ if(s.substr(0,s.size()/2)==s.substr(s.size()/2,s.size()/2)) return 1; return 0; } int main(){ int n; cin>>n; while(n--){ string s; cin>>s; int a=s.size(); if(a1) cout"NO" else if(a%2==0){ if(check(s)) cout"YES" else cout"NO" } else { int y=0; for(int i=0;i string s1=s.substr(0,i)+s.substr(i+1,a-i-1); if(check(s1)){ cout"YES" y=1; break; } } if(!y) cout"NO" } } return 0; }` C++ B. POI2010 Beads 这题首先计算前缀哈希和后缀哈希， 然后枚举 k 的值，对于每个 k 枚举 \frac{n}{k} 。 通过预处理的哈希前缀与后缀查询子数组是否存在。 但是这道题卡单哈希，要用双重哈希。 时间复杂度 ≤O(nlogn)。 代码： #include using namespace std; #define ull unsigned long long const int mod1=1e9+7; const int mod2=1e9+3; const int di1=13331; const int di2=131; const int N=2e5+5; int n,maxk,ans; int a[N],k[N]; map,bool>hsh; ull pw1[N],pw2[N],top1[N],top2[N],back1[N],back2[N]; void init(){ pw1[0]=pw2[0]=1; for(int i=1;i>n; for(int i=1;i>a[i]; init(); for(int i=1;n/i>=maxk;i++){ hsh.clear(); int now=0; for(int j=i;jmaxk) maxk=now,ans=1,k[ans]=i; else if(now==maxk) k[++ans]=i; } cout `#include using namespace std; #define ull unsigned long long const int mod1=1e9+7; const int mod2=1e9+3; const int di1=13331; const int di2=131; const int N=2e5+5; int n,maxk,ans; int a[N],k[N]; map,bool>hsh; ull pw1[N],pw2[N],top1[N],top2[N],back1[N],back2[N]; void init(){ pw1[0]=pw2[0]=1; for(int i=1;i pw1[i]=pw1[i-1]*di1%mod1, pw2[i]=pw2[i-1]*di2%mod2, top1[i]=(top1[i-1]*di1+a[i])%mod1, top2[i]=(top2[i-1]*di2+a[i])%mod2; for(int i=n;i;i--) back1[i]=(back1[i+1]*di1+a[i])%mod1, back2[i]=(back2[i+1]*di2+a[i])%mod2; } int main(){ cin>>n; for(int i=1;i>a[i]; init(); for(int i=1;n/i>=maxk;i++){ hsh.clear(); int now=0; for(int j=i;j int d1=(top1[j]-top1[j-i]*pw1[i]%mod1+mod1)%mod1; int d2=(top2[j]-top2[j-i]*pw2[i]%mod2+mod2)%mod2; if(!hsh.count({d1,d2})){ now++; hsh[{d1,d2}]=1; d1=(back1[j-i+1]-back1[j+1]*pw1[i]%mod1+mod1)%mod1; d2=(back2[j-i+1]-back2[j+1]*pw2[i]%mod2+mod2)%mod2; hsh[{d1,d2}]=1; } } if(now>maxk) maxk=now,ans=1,k[ans]=i; else if(now==maxk) k[++ans]=i; } cout" " for(int i=1;ik[i]" "; return 0; }` C++