\(\color{red}{\text{Spoiler Alert}_{{}_{{}^{{}^{ promax}}}}}\)

\(\color{red}{\text{Khuyến khích bạn đọc trước khi đọc phần lời giải xin hãy thử code ra thuật của mình dù nó có sai hay đúng}}\)

\(\color{red}{\text{Sau đó từ phần bài giải và thuật toán trước đó mà đối chiếu, rút nhận xét với thuật của mình và thu được bài học (không lãng phí thời gian đâu).}}\)

\(\color{blue}{\text{Công thức QHD : }dp[j] = dp[j] + dp[i - 1] \text{ khi đoạn A(i,j) xuất hiện trong B}}\)

\(\color{orange}{\text{Subtask 1}}\)

• So sánh đoạn con \(A(i,j)\) và \(B(p,p + j - i + 1)\)
• Duyệt lần lượt \(i\) và \(j\) với \((i \le j)\) sau đó duyệt \(p(p \le |B|)\) và \(q(p \le q \le p + j - i + 1)\).
• \(\color{purple}{\text{Độ phức tạp : } O(|A|^2 * |B|^2)}\)

\(\color{orange}{\text{Subtask 2}}\)

• Chúng ta sẽ sử dụng thuật toán \(hash\) để so sánh \(A(i,j)\) và \(B(p,p + j - i + 1)\) trong \(O(1)\).
• \(\color{purple}{\text{Độ phức tạp : } O(|A|^2 * |B|)}\)

\(\color{orange}{\text{Subtask 3}}\)

• Đẩy tất cả mã \(hash\) của các đoạn con trong \(B\) lên \(map\).
• Khi đó tìm đoạn \(A(i,j)\) có trong \(B\) hay không chỉ mất \(O(log((|B| * (|B| - 1))/2))\).
• \(\color{purple}{\text{Độ phức tạp : } O(|A|^2 * log((|B| * (|B| - 1))/2))}\)

\(\color{orange}{\text{Subtask 4}}\)

• Sử dụng \(Binary-Search\) lên \(i\) phân để tìm ra đoạn con \(A(i,j)\) xuất hiện trong \(B\) là dài nhất.
• Lúc này \(dp_j = dp_{j - 1} + dp_{j - 2} + ... + dp_{i - 1}\) vì \(A(i,j)\) xuất hiện trong \(B\) thì \(A(i + k(1 \le k \le j - i),j)\) cũng xuất hiện trong \(B\).
• Sử dụng mảng \(prefix\) với \(prefix_i = dp_1 + dp_2 + ... + dp_i\) để có thể tính \(dp_{j - 1} + dp_{j - 2} + ... + dp_{i - 1}\) trong \(O(1)\).
• \(\color{purple}{\text{Độ phức tạp : } O(|A| * log(|A|) * log((|B| * (|B| - 1))/2))}\)

\(\color{orange}{\text{Subtask 5}}\)

• Áp dụng \(Two-pointer\) thay vì \(Binary-Search\).
• Sử dụng \(SuffixArray\) lên xâu \(B\).
• Khi đó chúng ta sẽ tìm \(A(i,j)\) có xuất hiện trong \(B\) hay không với độ phức tạp là \(O(log(|B|) * (j - i + 1))\).
• Sử dụng thuật toán \(hash\) để giảm độ phức tạp.
• Khi đoạn \(A(i,i + mid)\) xuất hiện trong \(B\) thì tăng \(mid\), ngược lại thì giảm \(mid\).
  
  C++

      while (L1 <= R1){
          int mid1 = (L1 + R1) >> 1;
          if (mid1 - sa[mid] > y - x) R1 = mid1 - 1;
          else{
              ll v = GetHash_B(sa[mid],mid1) , u = GetHash_A(x,x + mid1 - sa[mid]);
              if (v == u) L1 = mid1 + 1;
              else R1 = mid1 - 1;
          }
      }
  

• \(\color{purple}{\text{Độ phức tạp : } O(2*|A|*log(|A|)*log(|B|))}\)