Clairewd's message /// 字符串hash

时间：2024-12-12 13:05:26

题目大意：

给定字符串s 是26个字母对应的密文字母

给定字符串c1 是 密文+部分原文

原文可能缺损 要求将原文补全输出

利用s得到密文字母对应的原字母rs

利用rs翻译c1得到 原文+部分密文c2

由于密文肯定是完整的 此时

c1 完整密文+部分原文

c2 完整原文+部分密文

将两个字符串hash 若一段字符相等则对应段的hash值也相等

枚举原文的长度 就可以得到在c1中原文的开始位置len

则此时假设 c1中 n-len+1~n 为原文 则c2中1~len为原文

若此时这两段字符的hash值相等 则假设成立

#include <bits/stdc++.h>

using namespace std;

#define LL long long

#define ULL unsigned long long

#define INF 0x3f3f3f3f

#define mem(i,j) memset(i,j,sizeof(i))

#define inc(i,l,r) for(int i=l;i<=r;i++)

#define dec(i,r,l) for(int i=r;i>=l;i--)

#define gcd(i,j) __gcd(i,j);

const int maxn=1e5+;

const int mod=1e9+;

const double eps=1e-;

typedef unsigned long long ull;

struct hash_table{

  ull seed=;

  ull Hash[maxn],temp[maxn];

  void work(char *s,int n){

    temp[]=; Hash[]=;

    for(int i=;i<=n;i++)temp[i]=temp[i-]*seed;

    for(int i=;i<=n;i++)Hash[i]=(Hash[i-]*seed+(s[i]-'a'));

  }

  ull get(int l,int r){

    return Hash[r]-Hash[l-]*temp[r-l+];

  }

}h1, h2;

char c1[maxn],c2[maxn];

char s[],rs[];

int main()

{

    int _; scanf("%d",&_);

    while(_--) {

        scanf("%s%s",s,c1+);

        inc(i,,-) rs[s[i]-'a']=i+'a';

        int n=strlen(c1+);

        inc(i,,n) c2[i]=rs[c1[i]-'a'];

        h1.work(c1,n); h2.work(c2,n);

        // h1对应的 c1是完整密文+部分原文

        // h2对应的 c2是完整原文+部分密文

        int ans=n;

        inc(i,n,n*-) { // 枚举整串的长度

            if(i&) continue; // 奇数长度跳过

            int mid=i/; // 得到此时密文的长度

            int len=n-mid; // 再得到部分原文的长度

            ULL s1=h1.get(n-len+,n); // 部分原文的密文

            ULL s2=h2.get(,len); // 部分原文

            if(s1==s2) { ans=mid; break; }

            // 若两个区间hash值相同 说明两段字符相同

        }

        inc(i,,ans) printf("%c",c1[i]);

        inc(i,,ans) printf("%c",c2[i]);

        printf("\n");

    }

    return ;

}

相关文章