字符串算法应用

用户头像 发布于 2025-08-07 49 次阅读 OI

S+字符串算法应用

A. 大厨的特色菜

这题直接分类讨论+暴力即可。
首先，当字符串长度小于 2 时，是肯定不满足条件的。
当字符串长度是偶数时，直接判断字符串前半段与后半段是否相等。
如果字符串长度是奇数，那么就枚举删除哪一个字符，再按照长度为偶数是的判断方法来判断即可。

#include<bits/stdc++.h>
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<=1) cout<<"NO"<<endl;
        else if(a%2==0){
            if(check(s)) cout<<"YES"<<endl;
            else cout<<"NO"<<endl;
        }
        else {
            int y=0;
            for(int i=0;i<a;i++){
                string s1=s.substr(0,i)+s.substr(i+1,a-i-1);
                if(check(s1)){
                    cout<<"YES"<<endl;
                    y=1;
                    break;
                }
            }
            if(!y) cout<<"NO"<<endl;
        }
    }
    return 0;
}
C++

B. POI2010 Beads

这题首先计算前缀哈希和后缀哈希，
然后枚举 $k$ 的值，对于每个 $k$ 枚举 $\frac{n}{k}$ 。
通过预处理的哈希前缀与后缀查询子数组是否存在。
但是这道题卡单哈希，要用双重哈希。
时间复杂度 $≤O(nlogn)$。
代码：

#include<bits/stdc++.h>
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<pair<ull,ull>,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;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<=n;i++) cin>>a[i];
    init();
    for(int i=1;n/i>=maxk;i++){
        hsh.clear();
        int now=0;
        for(int j=i;j<=n;j+=i){
            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<<maxk<<" "<<ans<<endl;
    for(int i=1;i<=ans;i++) cout<<k[i]<<" ";
    return 0;
}
C++