---
author: nguyencter
tags: Str2n
title: Str2n Solution
---

$\Huge\text{Str2n Solution}$

-------

:::info
🔗 Links: [Đề bài](https://drive.google.com/file/d/1V_mARG9nDxWdDzUUWOscyDKWzogD1M55/view?usp=sharing)
📌 Tags: `greedy`
✍️ Writer: nguyencter
📋 Content:
[TOC]
:::

-----

## Giới Thiệu Đề Bài

Khi học về xâu kí tự, để luyện tập thêm về nội dung này, An và Bình cùng nhau chơi mộ trò chơi với các xâu kí tự như sau:

- An tạo ra xâu kí tự ngẫu nhiên, sau đó, mỗi xâu ban đầu tạo ra một xâu mới bằng cách sao chép một đoạn đầu (hoặc toàn bộ) của xâu đó để tạo thêm được $n$ xâu.
- Với $2n$ xâu mà An tạo ra và được đánh số theo thứ ngẫu nhiên từ 1 đến $2n$, Bình cần đưara một phương án để giải thích cách tạo xâu của An.

**Yêu cầu:** Cho $2n$ xâu, hãy chia $2n$ xâu thành $n$ nhóm, mỗi nhóm gồm hai xâu mà xâu này là đoạn đầu (hoặc toàn bộ) của xâu kia.

-----

## Thuật toán

Một xâu mới được tạo ra bằng cách sao chép đoạn đầu hoặc toàn bộ xâu gốc nên độ dài xâu mới được tạo ra luôn bé hơn hoặc bằng độ dài xâu gốc.

Vì vậy ta chỉ cần sắp xếp lại mảng giảm dần theo độ dài xâu và với mỗi xâu ta tìm xâu có tiền tố giống nhau dài nhất với xâu đang xét.

Cụ thể ta dùng mảng $f$ lưu lại các xâu đôi một phân biệt và sắp xếp giảm dần theo độ dài xâu.

Sử dụng thêm một $map<str,vector<ll>> m$ để lưu thứ tự xuất hiện của các xâu.

Duyệt từ trái qua phải mảng $f$ với mỗi phần tử ta kiểm tra:
- Nếu $2 \leq m[f[i]]$ thì in ra $2$ vị trí xuất hiện của xâu $f[i]$ và xóa đi $2$ phần tử vừa in ra của vector $m[f[i]]$.
- Nếu $m[f[i]]=1$ thì cho $s=f[i]$ và xóa đi kí tự cuối của $s$ cho đến khi $m[s]!=0$ thì in ra ví trí xuất hiện của xâu $s$ và xâu $f[i],$ xóa đi phần tử vừa in ra của 2 vector $m[s]$ và $m[f[i]]$.
- Tiếp tục cho đến khi $m[f[i]].size()=0$.

----
Độ phức tạp là: $10^6*log(10^6)$.

Tham khảo code ở [đây](https://github.com/nguyencter/CODE/blob/main/Str2n.cpp)