3/17补题

E题 uva 12338

求两串的最长公共前缀

因为T很小其实可以裸上exkmp，然而现场写炸了qaq

exkmp的板子+ac代码

void pre_EKMP(char x[],int m,int next[]){
    next[0]=m;
    int j=0;
    while(j+1<m&&x[j]==x[j+1])j++;
    next[1]=j;
    int k=1;
    for(int i=2;i<m;i++){
        int p=next[k]+k-1;
        int L=next[i-k];
        if(i+L<p+1)next[i]=L;
        else{
            j=max(0,p-i+1);
            while(i+j<m&&x[i+j]==x[j])j++;
            next[i]=j;
            k=i;
        }
    }
}
void EKMP(char x[],int m,char y[],int n,int next[],int extend[]){
    pre_EKMP(x,m,next);
    int j=0;
    while(j<n&&j<m&&x[j]==y[j])j++;
    extend[0]=j;
    int k=0;
    for(int i=1;i<n;i++){
        int p=extend[k]+k-1;
        int L=next[i-k];
        if(i+L<p+1)extend[i]=L;
        else{
            j=max(0,p-i+1);
            while(i+j<n&&j<m&&y[i+j]==x[j])j++;
            extend[i]=j;
            k=i;
        }
    }
}

via kuangbin

//#define LOCAL
#include <cstring>
#include <iostream>
#include <sstream>
#include <fstream>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <algorithm>
#include <functional>
#include <utility>
#include <bitset>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstdio>
using namespace std;
#define X_mem(x,y,z) (X_mem[x][y][z] ? X_mem[x][y][z] :X_mem[x][y][z]=mem(x,y,z))
// X_INIT=0  mem_Macro
#define INF (1<<29)
#define MOD 1000000007ll
#define FOR(i,j,k) for(int i=j;i<=k;i++)
#define FORD(i,j,k) for(int i=j;i>=k;i--)
#define ll long long
#define ull unsigned long long 
#define SZ(x) int(x.size())
#define pb push_back
ull Hash,seed=131;
vector<ull>v[maxn];
char s[maxn];
int main(){
#ifdef LOCAL
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
#endif
int t,ii=1;
    scanf("%d",&t);
    while(t--)
    {
        int n,m,i,j,a,b;
        scanf("%d",&n);
        for(i=0;i<n;i++)
        {
            scanf("%s",s);
            v[i+1].clear();
            for(j=0,Hash=0;s[j];j++)
            {
                Hash=Hash*seed+s[j]-'a';
                v[i+1].push_back(Hash);
            }
        }
        scanf("%d",&m);
        printf("Case %d:
",ii++);
        while(m--)
        {
            scanf("%d%d",&a,&b);
            int l=0,r=min(v[a].size(),v[b].size())-1,ans=0;
            while(l<=r)
            {
                int mid=(l+r)>>1;
                if(v[a][mid]==v[b][mid]) l=mid+1,ans=mid;
                else r=mid-1;
            }
            if(v[a][ans]!=v[b][ans])
                printf("%d
",ans);
            else printf("%d
",ans+1);
        }
    }
//system("pause");
#ifdef LOCAL
fclose(stdin);
fclose(stdout);
#endif
return 0;
}

ac代码

B题 HYSBZ 3916

枚举删除位置检查答案

裸hash题。。。各种被hack。。。

//#define LOCAL
#include <cstring>
#include <iostream>
#include <sstream>
#include <fstream>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <algorithm>
#include <functional>
#include <utility>
#include <bitset>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstdio>
using namespace std;const ull base=233;
#define X_mem(x,y,z) (X_mem[x][y][z] ? X_mem[x][y][z] :X_mem[x][y][z]=mem(x,y,z))
// X_INIT=0  mem_Macro
#define INF (1<<29)
#define MOD 2333347
#define FOR(i,j,k) for(int i=j;i<=k;i++)
#define FORD(i,j,k) for(int i=j;i>=k;i--)
#define ll long long
#define ull unsigned long long 
#define SZ(x) int(x.size())
#define pb push_back
#define maxn 2000010
char s[maxn];
int n,len,hashmap[MOD+2],ans;
ull Hash[maxn],p[maxn];
inline ull gethash(int x,int y)
{
    if(x>y)return 0;
    return Hash[y]-Hash[x-1]*p[y-x+1];
}
inline int check(int pos)
{
    ull hasha,hashb;
    if(pos<=n+1)hasha=Hash[pos-1]*p[n+1-pos]+gethash(pos+1,n+1),hashb=gethash(n+2,len);
    else hasha=Hash[n],hashb=gethash(n+1,pos-1)*p[len-pos]+gethash(pos+1,len);
    if(hasha==hashb)
    {
        hashmap[hasha%MOD]++;
        if(hashmap[hasha%MOD]==1)ans++;
        return 1;
    }
    return 0;
}
int main(){
#ifdef LOCAL
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
#endif
     scanf("%d",&n);
    len=n;
    if(!(n&1))
    {
        printf("NOT POSSIBLE");
        return 0;
    }
    n/=2;
    scanf("%s",s+1);
    p[0]=1;
    for(int i=1;i<=len;++i)p[i]=p[i-1]*base,Hash[i]=Hash[i-1]*base+(s[i]-'A'+1);
    int pos;
    for(int i=1;i<=len;++i)if(check(i))pos=i;
    if(!ans)printf("NOT POSSIBLE");
    else if(ans>1)printf("NOT UNIQUE");
    else
    {
        if(pos>n+1)for(int i=1;i<=n;++i)printf("%c",s[i]);
        else for(int i=n+2;i<=len;++i)printf("%c",s[i]);
    }
//system("pause");
#ifdef LOCAL
fclose(stdin);
fclose(stdout);
#endif
return 0;
}

ac代码

以后要考虑改用非种子的hash了

比如这种

while(*str){
hash-(*str++)+(hash<<6)+(hash<<!6)-hash;
}
return hash & 0x7FFFFFF;

hash(str)=Σ₀^len-1si*65599ⁱmod 2³¹

满足可加性

其中h_ab=h_a*h_b*65599^lena mod 2³¹