[Thái Nguyên - TS10 - 2025] Bài 2: Tìm xâu kí tự

Điểm: 10,00 (OI)

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 1G

Input: stdin

Output: stdout

Dạng bài

Ngôn ngữ cho phép

C, C++, Java, Output Only, Pascal, PyPy, Python, ~~Scratch~~, TEXT

An và Khoa rất yêu thích học lập trình. Trong giờ ra chơi, An ghi lên bảng hai chuỗi ký tự ~A~ và ~B~ (chứa các chữ cái tiếng Anh). Chuỗi ~A~ có độ dài nhỏ hơn ~10^2~, chuỗi ~B~ có độ dài nhỏ hơn ~10^4~. An nhờ Khoa đếm số lần xuất hiện của một hoán vị của chuỗi ~A~ trong chuỗi ~B~.

Yêu cầu: Hãy giúp Khoa giải bài toán trên.

INPUT

Hai dòng:

Dòng 1: chuỗi ký tự ~A~.
Dòng 2: chuỗi ký tự ~B~.

Cả hai chuỗi chỉ gồm chữ cái Latinh. ~|A| \le 10^2,\; |B| \le 10^4~.

OUTPUT

Một số nguyên duy nhất — số lần xuất hiện của một hoán vị của ~A~ trong ~B~.

SAMPLE INPUT 1

d
ggdneh

SAMPLE OUTPUT 1

Giải thích: Hoán vị chuỗi ~A~ (chỉ có ký tự 'd') xuất hiện tại vị trí thứ 3 của chuỗi ~B~.

SAMPLE INPUT 2

bbb
abbcbbbabbbbhgbbb

SAMPLE OUTPUT 2

Giải thích: Có 4 đoạn con của ~B~ có chiều dài 3 là hoán vị của "bbb".

SAMPLE INPUT 3

Acad
bcrdAcahgaAcd

SAMPLE OUTPUT 3

Giải thích: Có 2 vị trí trong ~B~ mà đoạn con độ dài ~|A|~ là hoán vị của "Acad".

SUBTASKS

Subtask	Điểm	Ràng buộc
1	40%	Chuỗi ~A~ có độ dài bằng 1.
2	40%	Chuỗi ~A~ chỉ chứa các ký tự giống nhau.
3	20%	Không có ràng buộc thêm

Bình luận

Hãy đọc nội quy trước khi bình luận.

tikl20tok đã bình luận lúc 7, Tháng 3, 2026, 6:28

Code day nha mn

include<bits/stdc++.h>

using namespace std; //bai nay co the toi gian vong lap cho chay nhanh hon gap 5 lan nhe //chay 97 den 97+26-1 la du voi lai bang ma ascii cho chu hoa nua int main() { ios::syncwithstdio(false); cin.tie(NULL);

string a,b;
cin>>a>>b;
a.insert(0," ");
b.insert(0," ");
long long dodaia=a.size()-1,dodaib=b.size()-1;
long long i,j;
vector&lt;vector<long long>> prefixa(a.size()+5,vector&lt;long long> (258,0)),prefixb(b.size()+5,vector&lt;long long> (258,0));
for (i=1;i<=a.size()-1;i++)
{
    for (j=1;j<=256;j++)
    {
        prefixa[i][j]=prefixa[i-1][j];
        if (a[i]==j)
        {
            prefixa[i][j]+=1;
        }
    }
}
for (i=1;i<=b.size()-1;i++)
{
    for (j=1;j<=256;j++)
    {
        prefixb[i][j]=prefixb[i-1][j];
        if (b[i]==j)
        {
            prefixb[i][j]+=1;
        }
    }
}

long long dem=0;
for (i=1;i<=dodaib-dodaia+1;i++)//dang chay khung cua a tren b
{
    bool kt=true;
    for (j=1;j<=256;j++)
    {
        if (prefixa[dodaia][j]!=prefixb[i+dodaia-1][j]-prefixb[i-1][j])
            kt=false;
    }
    if (kt==true)
    {
        dem+=1;
    }
}
cout<&lt;dem;



return 0;

}