Xâu con

View as PDF
Submit solution
Points: 0.09 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout
Problem types
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Cho xâu ~A~ và xâu ~B~ chỉ gồm các chữ cái thường. Xâu ~B~ được gọi là xuất hiện tại vị trí ~i~ của xâu ~A~ nếu: ~A_{i} = B_1~, ~A_{i+1} = B_2~, ..., ~A_{i+length( B )-1} = B_{length( B )}~.

Hãy tìm tất cả các vị trí mà ~B~ xuất hiện trong ~A~.

Input

  • Dòng ~1~: xâu ~A~.
  • Dòng ~2~: xâu ~B~.

Độ dài ~A~, ~B~ không quá ~1000000~.

Output

  • Ghi ra các vị trí tìm được trên ~1~ dòng (thứ tự tăng dần). Nếu ~B~ không xuất hiện trong ~A~ thì bỏ trắng.

Sample Input

aaaaa
aa

Sample Output

1 2 3 4

Comments

Please read the guidelines before commenting.


  • 0
    NguyenTuanKieT_K66  commented on Nov. 13, 2025, 3:30 p.m.

    include <bits/stdc++.h>

    define ll long long

    using namespace std; ll hashT[1000005],poww[1000005]; string p,t; ll gethash(ll i,ll j) { return hashT[j]-hashT[i-1]poww[j-i+1]; } int main() { cin>>t>>p; ll hashP=0; for(ll i=0;i<p.size();i++) hashP=((hashP26)+p[i]); poww[0]=1; hashT[0]=0; for(ll i=1;i<=t.size();i++){ poww[i]=(poww[i-1]26); hashT[i]=(hashT[i-1]26)+t[i-1]; } for(ll i=1;i<=t.size()-p.size()+1;i++) if(gethash(i,i+p.size()-1)==hashP)cout<<i<<" "; return 0; }


  • 0
    nhanleff  commented on Nov. 8, 2025, 8:38 a.m.

    Code Automaton: https://www.ideone.com/lKVhGl


  • -4
    namta1082012  commented on Sept. 26, 2025, 2:19 p.m.

    Code c++ nhe moi nguoi :(Hoi Kho):

    include <bits/stdc++.h>

    using namespace std;

    int main() { ios::syncwithstdio(false); cin.tie(nullptr);

    string s, t;
if (!(cin >> s >> t)) return 0;
int n = s.size(), m = t.size();
vector<int> pi(m, 0);
for (int i = 1; i < m; i++) {
    int j = pi[i-1];
    while (j > 0 && t[i] != t[j]) j = pi[j-1];
    if (t[i] == t[j]) j++;
    pi[i] = j;
}
vector<int> res;
int j = 0;
for (int i = 0; i < n; i++) {
    while (j > 0 && s[i] != t[j]) j = pi[j-1];
    if (s[i] == t[j]) j++;
    if (j == m) {
        res.push_back(i - m + 2); 
        j = pi[j-1];
    }
}
for (int i = 0; i < (int)res.size(); i++) {
    if (i) cout << ' ';
    cout << res[i];
}
cout << '\n';

return 0;

    }


  • -5
    vominhmanh10  commented on Sept. 16, 2025, 12:36 p.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


  • -3
    2024_VoBaoNam  commented on June 19, 2025, 2:38 p.m.

    best with Z algo


  • 10
    HeroMinhSteve  commented on May 20, 2025, 8:03 a.m.

    Thấy cmt chưa có Z nên mình góp cho vui hihi

    https://ideone.com/VbQFEz


  • 2
    nongquan  commented on May 7, 2025, 9:10 a.m.

    mn tham khao : https://ideone.com/C0VlS7


  • -5
    nehuy7410  commented on March 13, 2025, 12:48 p.m. ← edit 2

    This comment is hidden due to too much negative feedback. Show it anyway.


  • -5
    keelythuytrang  commented on Jan. 8, 2025, 4:42 p.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


  • -3
    minhkochamhoc  commented on Jan. 8, 2025, 1:55 p.m.

    test cuối lấy sao vậy ạ mình bị TLE rồi :<


  • -1
    Dinh_Phuc_Minh  commented on Dec. 26, 2024, 2:37 p.m.

    dung KMP.


  • -12
    anhtuancabun  commented on July 13, 2024, 2:31 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


  • -172
    phu142857  commented on July 13, 2021, 3:00 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.


  • 60
    PPAP_1264589  commented on June 13, 2021, 5:22 p.m.

    Nếu dùng thuật Hash các bạn chú ý để long long nhé. Base cũng không nên quá lớn


    • 9
      NguyenHuuNhatQuang  commented on Oct. 29, 2022, 5:05 a.m.

      Hash thì để mod vừa phải và int cũng được để buff tốc độ chạy mặc dù không quá nhiều :D


    • 15
      kazamahoang  commented on July 2, 2021, 1:57 p.m.

      Tại sao vậy bạn


      • 25
        PPAP_1264589  commented on July 4, 2021, 2:23 p.m.

        Bởi trường hợp xấu nhất việc lấy mã hash có thể tràn số do vượt quá kiểu int :/

        Base không nên quá lớn cũng vì lý do này (theo kinh nghiệm của mình) :D


        • 7
          kazamahoang  commented on July 5, 2021, 9:50 a.m. ← edited

          Thế tràn bộ nhớ thì sao bạn

          với cả base không lớn thì sai số á :((


          • -43
            abcd1234  commented on Jan. 9, 2022, 2:06 p.m. ← edited

            This comment is hidden due to too much negative feedback. Show it anyway.