CF985F Isomorphic Strings (字符串Hash,巧解)

题目链接

题意翻译

给你一个长度为 $n$ 的字符串,$m$ 次询问.

问两个相同长度的子串是否匹配.

我们称两个子串是匹配的,当且仅当其满足:

其中一个子串的字母可替代另一个子串的字母

例如,我们称 $orzzz$ 和 $yzkkk$ 是匹配的,因为其满足交换条件:

$o$ -> $y$

$r$ -> $z$

$z$ -> $k$

所以它们是匹配的.

同时输入中前两个为子串起点,最后一个为子串长度.

Solution

先补充一个知识点,子串哈希的性质:

若已知一个$|S|=n$的字符串的 $hash$ 值, $hash[i],1≤i≤n,$ 其子串 $sl..sr,1≤l≤r≤n$ ; 其中 $hash[i]$ 代表其从开始到第 $i$ 位的 $hash$ 值

对应的hash值为：

\[hash=hash[r]-hash[l-1]*p^{r-l+1}
\]

考虑到$hash[i]$每次对$p$取模,进一步得到下面的式子：

\[hash=(hash[r]-hash[l-1]*p^{r-l+1}+p)mod p
\]

至此得到求子串 $hash$ 值公式.

然后看**这道题的做法:**
我们先将所有相同的字母单独拎出来组成一个新的字符串,其余字符的位置补成$0$.

给一个例子:

$aaaba$ 和 $cccdc$

对于第一个子串:

$a:11101$

$b:00010$

第二个子串:

$c:11101$

$d:00010$

然后我们发现$a$与$c$的$Hash$值是相同的。

$b$和$d$也是相同的,然后就匹配成功。

然后在每次询问将子串里诸如此类的$Hash$值求出来。

排一遍序,然后$O(26)$找相同的即可,总体时间复杂度$O(n*26*log26).$

### Code
```cpp
#include
#define ll long long
using namespace std;
const int maxn=200008;
const ll seed=23;
const ll mod=19260817;
string ch;
int n,m;
ll hash[maxn][30];
ll cf[maxn];
ll a[30],b[30];

void pre()

{

for(int j=1;j<=26;j++)

for(int i=1;i<=n;i++)

{

ll fuck=0;

if(ch[i]=='a'+j-1)fuck='#';

hash[i][j]=((hash[i-1][j]seed)%mod+fuck)%mod;

}

cf[0]=1;

for(int i=1;i<=n;i++)

cf[i]=(cf[i-1]seed)%mod;

return;

}

void solve(int len,int s,int k)

{

for(int i=1;i<=26;i++)

{

a[i]=(hash[s+len-1][i]-(hash[s-1][i]cf[len]%mod)+mod)%mod;

b[i]=(hash[k+len-1][i]-(hash[k-1][i]cf[len]%mod)+mod)%mod;

}

sort(a+1,a+27);sort(b+1,b+27);

for(int i=1;i<=26;i++)

if(a[i]!=b[i]){cout<<"NO"<<endl;return;}

cout<<"YES"<<endl;

}

int main()

{

ch='*';

cin>>n>>m;

string s; cin>>s;

ch+=s;

pre();

for(int i=1;i<=m;i++)

{

int len,s,k;

scanf("%d%d%d",&s,&k,&len);

solve(len,s,k);

}

}

巴特西

CF985F Isomorphic Strings (字符串Hash,巧解)

题目链接

题意翻译

Solution

最新文章

热门文章