题解：CF119D String Transformation
考场思路，比较暴力。
实现
考虑将函数补上一个正常
那么此时前两部分以
具体地，维护四个哈希数组：
-
h1：
a 的后缀转置； -
h2：
a 的正常哈希； -
h3：断点字符串，指上文补全函数后的前两部分；
-
h4：
a 的前缀转置。
这四个都不难维护。
那么就可以写出原题函数的哈希值：
其中
显然此式子大部分只与
因为原式子除
考场代码，没删注释。
::::success[Code]
#include <bits/stdc++.h>
#define int long long
#define PII pair < int , int >
#define x first
#define y second
#define rg register
using namespace std ;
//bool bbb ;
// 字符集：32~126 ， 1~95
const rg int N = 1e6 + 5 ;
char a[N] , b[N] ;
const rg int B1 = 131 , P1 = 998244353 , B2 = 13331 , P2 = 1e9 + 7 ;
int pw1[N] , pw2[N] , inv1[N] , inv2[N] ;
inline int qpow(rg int a , rg int b , rg int p){
rg int res = 1 ;
while(b){
if(b & 1) res = res * a % p ;
b >>= 1 , a = a * a % p ;
}
return res ;
}
int i , j ;
inline void init(){
pw1[0] = pw2[0] = 1 ;
for(i = 1 ; i < N ; ++ i)
pw1[i] = pw1[i - 1] * B1 % P1 ,
pw2[i] = pw2[i - 1] * B2 % P2 ;
inv1[N - 1] = qpow(pw1[N - 1] , P1 - 2 , P1) ,
inv2[N - 1] = qpow(pw2[N - 1] , P2 - 2 , P2) ;
for(i = N - 2 ; ~i ; -- i)
inv1[i] = inv1[i + 1] * B1 % P1 ,
inv2[i] = inv2[i + 1] * B2 % P2 ;
}
struct Hash{
int hs1[N]{} , hs2[N]{} ;
inline void add(rg int x , rg int y , char d){
hs1[x] = (hs1[y] * B1 + d) % P1 ,
hs2[x] = (hs2[y] * B2 + d) % P2 ;
}
} h1 , h2 , h3 , h4 ; // h1 是 a 的后缀转置 hs，h2 是 a 的 hs，辅助，h3 是断点字符串 hs，h4 是 a 的前缀转置 hs，h5 是 b 的 hs
unordered_map < int , vector < int > > mp ;
//bool eee ;
signed main(){
// freopen("str.in" , "r" , stdin) ;
// freopen("str.out" , "w" , stdout) ;
ios :: sync_with_stdio(0) ;
cin.tie(0) ; cout.tie(0) ;
// cerr << "Memory: " << abs((char*)&eee - (char*)&bbb) / 1024.0 / 1024.0 << " MB\n" ;
init() ;
char c ; int n = 0 , m = 0 ;
while((c = getchar()) != '\n' && c != EOF && n < N - 1)
a[n ++] = c ;
while((c = getchar()) != '\n' && c != EOF && m < N - 1)
b[m ++] = c ;
if(n != m)
return cout << "-1 -1\n" , 0 ;
// cout << n << '\n' ;
rg int hsb1 = 0 , hsb2 = 0 ;
for(j = 0 ; j < n ; ++ j)
hsb1 = (hsb1 * B1 + b[j]) % P1 ,
hsb2 = (hsb2 * B2 + b[j]) % P2 ;
// for(int i = 0 ; i < n ; i++)
// cout << h5.hs1[i] << '\n' ;
for(i = n - 1 ; i >= 0 ; -- i)
h1.add(i , i + 1 , a[i]) ;
for(i = 0 ; i < n ; ++ i){
h2.add(i , i ? i - 1 : 0 , a[i]) ;
// cout << h2.hs1[i] << '\n' ;
h3.hs1[i] = (h2.hs1[i] * pw1[n - i - 1] + h1.hs1[i + 1]) % P1 ,
h3.hs2[i] = (h2.hs2[i] * pw2[n - i - 1] + h1.hs2[i + 1]) % P2 ;
// [0 , i] , [i + 1 , n-1] 的 hs，只用取断点前的后缀，就是说实际使用需要 - hs 的一段 hs
h4.hs1[i] = ((i ? h4.hs1[i - 1] : 0) + a[i] * pw1[i]) % P1 ,
h4.hs2[i] = ((i ? h4.hs2[i - 1] : 0) + a[i] * pw2[i]) % P2 ;
// 前缀 i 的转置 hs
}
// cout << h3.hs1[2] << ' ' << h2.hs1[1] * pw1[1] % P1 << " " << (h3.hs1[2] - h2.hs1[1] * pw1[2] % P1 + P1) % P1 << '\n' ;
// cout << ((h3.hs1[2] - h2.hs1[1] * pw1[1] % P1 + P1) % P1 * pw1[2] % P1 + h4.hs1[1]) % P1 << "\n" ;
for(j = 1 ; j < n ; ++ j){
int ky = h3.hs1[j - 1] * P2 + h3.hs2[j - 1] ;
mp[ky].emplace_back(j) ;
}
hsb1 += P1 , hsb2 += P2 ;
for(i = n - 2 ; i >= 0 ; -- i){
rg int x = ((hsb1 - h4.hs1[i]) * inv1[i + 1] + h2.hs1[i] * pw1[n - i - 1]) % P1 ,
y = ((hsb2 - h4.hs2[i]) * inv2[i + 1] + h2.hs2[i] * pw2[n - i - 1]) % P2 ,
ky = x * P2 + y ;
// rg int x = 0 , y = 0 ;
rg auto it = mp.find(ky) ;
if(it == mp.end()) continue ;
rg auto &v = it -> y ;
rg auto pos = upper_bound(v.begin() , v.end() , i) ;
if(pos != v.end())
return cout << i << ' ' << (*pos) << '\n' , 0 ;
}
return cout << "-1 -1\n" , 0 ;
}
/*
Die Polizei untersucht eine Straftat im IT-Bereich.
untersucht eine Straftat.hciereB-TI mi ieziloP eiD
cbaaaa
aaaabc
123342
3324212
abca
caba
*/
::::
发现有两个瓶颈：哈希表与二分。
前者换为手写哈希表，后者对于哈希表有值的位置换为双指针即可