Elearning CodePath – CTP Online Judge

Same "so"

SAMESO

🟢 Hard #General #String

### Thông tin chung

| Mục | Nội dung |
| --- | --- |
| **Tên Bài Toán** | **Same "so"** |
| **Input** | xâu $T$, xâu $S$. |
| **Output** | Số nguyên duy nhất là độ giống nhau giữa hai xâu |
| **File Input** | `SAMESO.INP` |
| **File Ouput** | `SAMESO.OUT` |

Hôm nay, God M đi học tiếng Anh để đi ôn tuyển GOI Trái Đất ở bên Moscow. Thầy giáo dạy trên bảng về cách phát âm từ "same" và "so". Thế nhưng God M lại tưởng thầy đang nói về same "xâu", thế là God ghé sang người bên cạnh mình, God H để nói chuyện về bài toán same "xâu" mà cậu mới làm hôm qua khi học online với QUANSENSEI.

Bài toán về cơ bản là dễ: Với hai xâu $X$ và $Y$ bất kì có độ dài bằng nhau, ta định nghĩa độ giống nhau của hai xâu là số vị trí mà hai kí tự tương ứng trên hai xâu giống nhau, tức là chỉ số $i$ thỏa mãn: $X_i = Y_i$.

Ví dụ: xâu `manhxbd` và xâu `mabhxha` có độ giống nhau là $4$.

Cho hai xâu $S$ có độ dài $n$ và $T$ có độ dài $m$ $(m \le n)$. Độ giống nhau giữa hai xâu $S$ và $T$ bằng tổng số độ giống nhau giữa xâu $T$ và mọi xâu con liên tiếp độ dài $m$.

God H thấy bài này cũng hay hay, và đã tìm được thuật toán cũng như chứng minh được độ phức tạp của thuật toán của mình là $O(\log_n(m))$ và có thể chạy tới $m,n <= \infty$. Nên God H đố bạn nghĩ ra và chứng minh được thuật toán tương tự.

##### <u>LƯU Ý:</u> nếu bạn không comment vào trong code để chứng minh thuật toán đúng và chứng minh độ phức tạp đủ nhỏ để qua thì bài của bạn sẽ không được chấm và God H sẽ đến gõ cửa nhà bạn vào tối nay.

### Định dạng đầu vào

- Dòng đầu ghi xâu $T$.
  
- Dòng thứ ghi xâu $S$.
  
- Các kí tự trong hai xâu thuộc $'a'...'z'$.
  
- $1 \le |T| \le |S| \le 2.10^6$.

### Định dạng đầu ra

- In ra trên một dòng duy nhất là độ giống nhau giữa xâu $S$ và xâu $T$.

### Ví dụ (Sample Test)

| Input (`SAMESO.INP`) | Output (`SAMESO.OUT`) |
| --- | --- |
| `abaab` <br/>`aababacab` | `12` |

### (Điều quan trọng phải nhắc lại 3 lần).

✅ Đã AC: 1 / 4 submissions