字符串hash

兔子和兔子

#include<iostream>
#include<string.h>
using namespace std;
typedef unsigned long long ull;
const int N = 1000010,base = 131;
ull h[N],p[N];
char s[N];

ull get(int i,int j){
    return h[j] - h[i-1]*p[j-i+1];
}

int main(){
    scanf("%s",s+1);
    p[0] = 1;
    int size = strlen(s+1);
    for(int i=1;i<=size;i++){
        h[i] = h[i-1]*base + s[i] - 'a' +1;
        p[i] = p[i-1] * base;
    }
    

    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        int l1,r1,l2,r2;
        cin>>l1>>r1>>l2>>r2;
        ull s1 = get(l1,r1);
        ull s2 = get(l2,r2);

        if(s1==s2)
            cout<<"Yes"<<endl;
        else
            cout<<"No"<<endl;
    }
    return 0;
}

最大回文子串

#include<iostream>
#include<string.h>
using namespace std;

typedef unsigned long long ull;
const int N = 2000010,base = 131;
ull p[N],hl[N],hr[N];
char s[N];

ull getl(int i,int j){
    return hl[j] - hl[i-1]*p[j-i+1];
}
ull getr(int i,int j){
    return hr[i] - hr[j+1]*p[j-i+1];
}

bool check(int x,int center){
    ull l = getl(center-x,center-1);
    ull r = getr(center+1,center+x);
    if(l==r) return true;
    return false;
}

int main(){
    int C = 0;
    while(scanf("%s",s+1),strcmp(s+1,"END")){
        C++;
        int n = strlen(s+1);
        for(int i = 2*n;i>0;i-=2){
            s[i] = s[i/2];
            s[i-1] = 'z'+1;
        }
        
        n = 2*n;

        p[0] = 1;
        for(int i=1,j=n;i<=n;i++,j--){
            hl[i] = hl[i-1]*base + s[i]-'a'+1;
            hr[j] = hr[j+1]*base + s[j]-'a'+1;
            p[i] = p[i-1]*base;
        }
        int res = 1;
        for(int i=1;i<=n;i++){
            int len = min(i-1,n-i);
            
            int l = 0,r= len;
            while(l-r){
                int mid = l+r+1>>1;
                if(check(mid,i)) l = mid;
                else r = mid -1;
            }

            if(s[i+l]>'z') res = max(res,l);
            else{
                res = max(res,l+1);
            }
        }
        
        printf("Case %d: %d\n",C,res);
    }
    return 0;
}

kmp
周期

#include<iostream>

using namespace std;
const int N = 1000010;
char s[N];
int Next[N];
int n;
void get_next(){
    int j = 0;
    for(int i=2;i<=n;i++){
        while(j&&s[i]!=s[j+1]) j = Next[j];
        if(s[i]==s[j+1]) j++;
        Next[i] = j;
    }
}

int main(){
    int C = 0;
    while(scanf("%d",&n),n){
        C++;
        scanf("%s",s+1);
        get_next();
        
        cout<<"Test case #"<<C<<endl;
        for(int i= 1;i<=n;i++){
            int t = i-Next[i];
            
            if(t!=i&&i%t==0) cout<<i<<" "<<i/t<<endl;
        }
        cout<<endl;
    }

}