题目问的是相对位置是否一样，即若 \(s\) 的第 \(1,2,3\) 个字符串相等，\(t\) 的第 \(1,2,3\) 个字符串也相等，则 \(s=t\)。
由于 \(t\) 的长度是固定的，所以我们使用哈希进行快速匹配。
那么如何设计哈希函数则成为本题的难点。
由于问相对位置，那么可以记 \(val[i]\) 表示第 \(i\) 个字符串上上一个相等的字符串间隔的距离，如果是第一个，则设置为 \(\infty\)，这样就能表示出关系了。
点击查看代码
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ULL;
typedef long long LL;
LL read() {
LL sum=0,flag=1; char c=getchar();
while(c<'0'||c>'9') {if(c=='-') flag=-1; c=getchar();}
while(c>='0'&&c<='9') {sum=sum*10+c-'0'; c=getchar();}
return sum*flag;
}
const int N=1e6+10;
const LL MOD1=998244353,MOD2=1e9+7,Base=13331,INF=1e9;
int n,m;
int val1[N],val2[N],nxt[N];
string s[N],t[N];
LL p1[N],p2[N];
LL hs1,hs2,ht1,ht2;
map<string,int> mp;
int main() {
while(cin>>s[++n]) {
if(s[n]=="$") {
n--;
break;
}
}
while(cin>>t[++m]) {
if(t[m]=="$"){
m--;
break;
}
}
for(int i=1;i<=n;i++) {
if(mp[s[i]]!=0) {
val1[i]=i-mp[s[i]];
nxt[mp[s[i]]]=i;
}
else {
val1[i]=INF;
}
mp[s[i]]=i;
if(i<=m) {
hs1=(hs1*Base+val1[i])%MOD1;
hs2=(hs2*Base+val1[i])%MOD2;
}
}
mp.clear();
p1[0]=1; p2[0]=1;
for(int i=1;i<=m;i++) {
if(mp[t[i]]!=0) {
val2[i]=i-mp[t[i]];
}
else {
val2[i]=INF;
}
mp[t[i]]=i;
ht1=(ht1*Base+val2[i])%MOD1;
ht2=(ht2*Base+val2[i])%MOD2;
p1[i]=p1[i-1]*Base%MOD1;
p2[i]=p2[i-1]*Base%MOD2;
}
if(hs1==ht1&&hs2==ht2) {
cout<<1<<endl; return 0;
}
for(int i=2;i+m-1<=n;i++) {
// for(int j=1;j<=n;j++) cout<<val1[j]<<' ';
// cout<<endl;
hs1=((hs1-val1[i-1]*p1[m-1])%MOD1+MOD1)%MOD1;
hs2=((hs2-val1[i-1]*p2[m-1])%MOD2+MOD2)%MOD2;
hs1=(hs1*Base+val1[i+m-1])%MOD1;
hs2=(hs2*Base+val1[i+m-1])%MOD2;
if(nxt[i-1]<=i+m-1) {
int l=i+m-1-nxt[i-1];
hs1=((hs1-val1[nxt[i-1]]*p1[l])%MOD1+MOD1)%MOD1;
hs2=((hs2-val1[nxt[i-1]]*p2[l])%MOD2+MOD2)%MOD2;
hs1=((hs1+INF*p1[l])%MOD1+MOD1)%MOD1;
hs2=((hs2+INF*p2[l])%MOD2+MOD2)%MOD2;
}
val1[nxt[i-1]]=INF;
if(hs1==ht1&&hs2==ht2) {
cout<<i;
return 0;
}
}
return 0;
}