牛客练习赛33 E tokitsukaze and Similar String （字符串哈希hash）-白红宇

牛客练习赛33 E tokitsukaze and Similar String （字符串哈希hash）

阅读量：5151 次

发布时间：2019-06-13

本文共 2194 字，大约阅读时间需要 7 分钟。

链接：

来源：牛客网

tokitsukaze and Similar String

时间限制：C/C++ 2秒，其他语言4秒

空间限制：C/C++ 262144K，其他语言524288K

64bit IO Format: %lld

题目描述

tokitsukaze获得了一个长度为n，由a-z小写字母组成的字符串。

我们定义两个字符串是相似的，当且仅当能通过多次以下操作，使得两个字符串相等。并且把需要操作的最小次数，称为两个字符串的相似度。

操作是这样的：选择一个字符串，把字符串的每个字母都替换为字母表上的下一个字母，同时，我们认为z的下一个字母为a，比如选择"acdz"，操作一次后变为"bdea"。

现在tokitsukaze从字符串中任取两个子串，她想知道它们是不是相似的，如果它们相似，请输出相似度，如果它们不相似，请输出-1。

输入描述:

第一行包括一个正整数n(1≤n≤10^5)，表示字符串长度。

第二行包括一个长度为n，且仅包含小写英文字母的字符串。

接下来一行包括一个正整数q(1≤q≤10^5)，表示询问次数。

接下来q行，每行包括3个正整数x，y，len。(1≤x，y≤n)，(1≤len≤n并且1≤x+len-1，y+len-1≤n)。表示查询子串[x...x+len-1]和子串[y...y+len-1]。

输出描述:

对于每个查询，输出一行，表示答案。

示例1

输入

复制

aabbcdedcz

1 3 2

2 6 2

4 6 4

1 10 1

输出

复制

-1

说明

第一个查询的子串为"aa"和"bb"，"aa"变为"bb"需要1次操作，所以相似度为1。

第二个查询的子串为"ab"和"de"，"ab"变为"de"需要3次操作，所以相似度为3。

第三个查询的子串为"bcde"和"dedc"，"bcde"不能变为"dedc"，所以两个字符串不相似，输出-1。

第四个查询的子串为"a"和"z"，"z"变为"a"需要1次操作，所以相似度为1。

题意：

思路：

字符串哈希，预处理26种变化的hash表，每次询问用hash表来判断子串是否相等，若x的第i次变化与y相等，ans=min(i,26-i)；

细节见代码：

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           #include 
            
             #include 
             
              #include 
              
               #define ALL(x) (x).begin(), (x).end()#define rt return#define dll(x) scanf("%I64d",&x)#define xll(x) printf("%I64d\n",x)#define sz(a) int(a.size())#define all(a) a.begin(), a.end()#define rep(i,x,n) for(int i=x;i
               
                #define pll pair
                
                 #define gbtb ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)#define MS0(X) memset((X), 0, sizeof((X)))#define MSC0(X) memset((X), '\0', sizeof((X)))#define pb push_back#define mp make_pair#define fi first#define se second#define eps 1e-6#define gg(x) getInt(&x)#define chu(x) cout<<"["<<#x<<" "<<(x)<<"]"<
                 
                  >n; cin>>str+1; pw[0]=1ll; repd(i,1,n) { repd(j,0,25) { f[i][j]=(f[i-1][j]*p+(str[i]-'a'+j+1)%26); if((str[i]-'a'+1+j)%26==0) { f[i][j]+=26; } } pw[i]=pw[i-1]*p; } int q; cin>>q; int x,y,len; while(q--) { cin>>x>>y>>len; int t=(str[y]-'a'+1+26-(str[x]-'a'+1))%26; if(get(x,x+len-1,t)==get(y,y+len-1,0)) { cout<
                  
                   <
                   
                    = '0' && ch <= '9') { *p = *p * 10 - ch + '0'; } } else { *p = ch - '0'; while ((ch = getchar()) >= '0' && ch <= '9') { *p = *p * 10 + ch - '0'; } }}

转载于:https://www.cnblogs.com/qieqiemin/p/11199920.html

你可能感兴趣的文章