You are given two strings $$$s, t$$$ of length $$$n$$$. Find the number of pairs $$$(l, r)$$$ of integers such that $$$1 \le l \le r \le n$$$ and the substring $$$s_ls_{l+1}s_{l+2}\ldots s_r$$$ is lexicographically smaller than $$$t_lt_{l+1}t_{l+2}\ldots t_r$$$.
A string $$$a$$$ is lexicographically smaller than a string $$$b$$$ if and only if one of the following holds:
The first line of the input contains a single integer $$$n$$$ ($$$1 \le n \le 200\,000$$$).
The second and the third lines of the input contain strings $$$s$$$, $$$t$$$ of length $$$n$$$ correspondingly, each consisting only of lowercase Latin letters.
Output a single integer — the number of pairs $$$(l, r)$$$ of integers such that $$$1 \le l \le r \le n$$$ and the substring $$$s_ls_{l+1}s_{l+2}\ldots s_r$$$ is lexicographically smaller than $$$t_lt_{l+1}t_{l+2}\ldots t_r$$$.
3 aab aba
4
4 icpc cool
4
4 zyzz life
0
7 trivial problem
16
18 goodluckandhavefun letthestrongestwin
112
In the first sample, there are $$$4$$$ such pairs: $$$(1, 2), (1, 3), (2, 2), (2, 3)$$$.
Name |
---|