CF2196E2 Fuzzy Concatenation (Hard version)

This is the hard version of the problem. The difference between the versions is that in this version, $ n \le 5 \cdot 10^{5}, m \le 5 \cdot 10^{4} $ . You can hack only if you solved all versions of this problem. There are two strings $ s $ and $ t $ , both consisting of lowercase Latin letters. You also have an empty string $ p $ . You can perform the following operation, which consists of several stages: - choose any two integers $ l $ and $ r $ ( $ 1 \le l \le r \le |s| $ ); - copy the substring $ s_{l},\ldots, s_{r} $ and append it to the end of string $ p $ ; - among the last $ r - l + 1 $ characters of string $ p $ , change at most one character to any lowercase Latin letter. For example, if the string $ s = $ "dhhtyhwbsl" and $ p = $ "", you can choose $ l = 3, r = 6 $ and add "htyh" to the end of $ p $ , and then change the character "y" to "a", resulting in $ p = $ "htah". Your task is to determine the minimum number of operations required for string $ p $ to become equal to $ t $ .

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 10^4 $ ). The description of the test cases follows. The first line of each test case contains two integers $ n $ and $ m $ ( $ 1 \le n \le 5 \cdot 10^{5}, 1 \le m \le 5 \cdot 10^{4} $ ) — the lengths of strings $ s $ and $ t $ . The second line of each test case contains the string $ s $ of length $ n $ , consisting of lowercase Latin letters. The third line of each test case contains the string $ t $ of length $ m $ , consisting of lowercase Latin letters. It is guaranteed that the sum of $ n $ across all test cases does not exceed $ 5 \cdot 10^{5} $ , and the sum of $ m $ across all test cases does not exceed $ 5 \cdot 10^{4} $ .

For each test case, output a single integer — the answer to the problem.

In the first test case, you can take the substring $ «\mathtt{a}» $ from the string $ s $ , change a single letter in this string to $ «\mathtt{b}» $ , and append it to the end of the string $ p $ , resulting in $ p $ becoming equal to $ t $ . In the second test case, $ t $ can be obtained in $ 3 $ operations as follows: $$$ «\mathtt{a\color{red}{b}}» + «\mathtt{\color{red}{z}}» + «\mathtt{\color{red}{b}a}» $$$ The modified characters are highlighted in red. In the third test case, the string $ t $ can be obtained as follows: $$$ «\mathtt{ht\color{red}{a}h}» + «\mathtt{bs\color{red}{e}}» + «\mathtt{htyh\color{red}{z}b}» $$$