Khớp xâu - LCOJ: Luyen Code Online

KHOPXAU - Khớp xâu

Điểm: 2,00 (OI)

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

Giới hạn bộ nhớ: 256M

Tác giả:

Hieu Nguyen

Dạng bài

Ngôn ngữ cho phép

C, C#, C++, Go, Java, Pascal, Perl, PHP, Python, Ruby, Rust, Scratch, Swift

Cho hai xâu ký tự ~s~ và ~t~ có độ dài lần lượt là ~n~ và ~m\ (m ≤ n)~. Xâu ~t~ được gọi là xuất hiện (khớp) tại vị trí ~i~ của xâu ~s~ nếu ~t = s[i..(i + m – 1)]~ (hay ~s[i] = t[1], ..., s[i + m – 1] = t[m]~).

Bạn được cho hai xâu ký tự ~s~ và ~t~ chỉ gồm các chữ cái Latinh thường (‘a’, …, ’z’). hãy liệt kê tất cả các vị trí trên xâu ~s~ mà xâu ~t~ xuất hiện.

Input

Dòng đầu chứa xâu ~s~;
Dòng thứ hai chứa xâu ~t~.

Giới hạn:

~1 ≤ |s|, |t| ≤ 10^6; |t| ≤ |s|~.

Output

Ghi trên một dòng các vị trí xuất hiện của xâu ~t~ trong xâu ~s~ (chỉ số của ký tự đầu tiên trong xâu là ~1~, các vị trí được liệt kê theo thứ tự tăng dần, hai số liên tiếp được ghi cách nhau một dấu cách).

Sample

Input #1

abababa
ba

Output #1

2 4 6

Problem source: Chuyên Sơn La Online Judge

Bình luận

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

c++ full ac

#include <iostream>
#include <map>

using namespace std;

int main() {
    string s1,s2;
    cin >> s1 >> s2;
    int m = s2.size();
    for (int i = 0; i < s1.size(); i++){
        string tmp = s1.substr(i,m);
        if (s2 == tmp){
            cout << i+1 << ' ';
        }
    }
    return 0;
}

4

hohoanghai5042011 đã bình luận lúc 20, Tháng 1, 2024, 9:52 ← sửa 2 →

include <iostream>

include <vector>

using namespace std; int main() { string A, B; cin >> A >> B; vector<int> positions; sizet found = A.find(B); while (found != string::npos) { positions.pushback(found + 1); found = A.find(B, found + 1);} for (int i : positions) cout << i << " "; return 0; } nó bị lỗi kiểu chữ mong mn thông cảm và admin mau sửa lỗi này. Code này mình đã nộp full ac có gì các bạn dùng AI để sửa lỗi từ vựng lại để chương trình chấm đúng. Mong mn cho mình 1 vote lên nhé

1

______ đã bình luận lúc 25, Tháng 1, 2024, 7:40

A Long hiền khô :)

1

Jayce đã bình luận lúc 11, Tháng 12, 2023, 0:29

Ai có bài giải cho mình tham khảo với