链接：https://ac.nowcoder.com/acm/contest/308/E

来源：牛客网

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

输入

复制

10

aabbcdedcz

4

1 3 2

2 6 2

4 6 4

1 10 1

输出

复制

1

3

-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 <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

#include <queue>

#include <stack>

#include <map>

#include <set>

#include <vector>

#include <iomanip>

#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<n;i++)

#define repd(i,x,n) for(int i=x;i<=n;i++)

#define pii pair<int,int>

#define pll pair<long long ,long long>

#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)<<"]"<<endl

using namespace std;

typedef long long ll;

ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a;}

ll lcm(ll a, ll b) {return a / gcd(a, b) * b;}

ll powmod(ll a, ll b, ll MOD) {ll ans = 1; while (b) {if (b % 2)ans = ans * a % MOD; a = a * a % MOD; b /= 2;} return ans;}

inline void getInt(int* p);

const int maxn = 100010;

const int inf = 0x3f3f3f3f;

/*** TEMPLATE CODE * * STARTS HERE ***/

ll p=12582917ll;

ll mod=1610612741ll;

unsigned long long f[maxn][35];

unsigned long long pw[maxn];

int n;

char str[maxn];

unsigned long long get(int l,int r,int t)

{

	return f[r][t]-f[l-1][t]*pw[r-l+1];

}

int main()

{

	//freopen("D:\\code\\text\\input.txt","r",stdin);

	//freopen("D:\\code\\text\\output.txt","w",stdout);

	gbtb;

	cin>>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<<min(t,26-t)<<endl;

		}else

		{

			cout<<-1<<endl;

		}

	}

	return 0;

}

inline void getInt(int* p) {

	char ch;

	do {

		ch = getchar();

	} while (ch == ' ' || ch == '\n');

	if (ch == '-') {

		*p = -(getchar() - '0');

		while ((ch = getchar()) >= '0' && ch <= '9') {

			*p = *p * 10 - ch + '0';

		}

	}

	else {

		*p = ch - '0';

		while ((ch = getchar()) >= '0' && ch <= '9') {

			*p = *p * 10 + ch - '0';

		}

	}

}