SUFIX - Hậu tố chung dài nhất

Xem dạng PDF
Gửi bài giải
Điểm: 2,00 (OI)
Giới hạn thời gian: 0.05s
Giới hạn bộ nhớ: 256M
Tác giả:
Hiếu Nguyễn
Dạng bài
Ngôn ngữ cho phép
C, C#, C++, Go, Java, Pascal, Perl, PHP, PyPy, Python, Ruby, Rust, Scratch, Swift

Cho xâu ký tự ~s~ có độ dài ~n~. Với mỗi ~1 ≤ i ≤ n~ ta gọi ~f(i)~ là độ dài của xâu hậu tố chung dài nhất của ~s~ và ~s[1..i]~, tức là nếu ~f(i) = k~ thì ~s[i] = s[n], s[i – 1] = s[n – 1], …, s[i – k + 1] = s[n – k + 1]~ và ~s[i – k] ≠ s[n – k]~.

Bạn được cho xâu ký tự ~s~ chỉ gồm các chữ cái Latinh thường (‘a’, …, ’z’) và ~m~ chỉ số ~i_1, i_2, …, i_m~. Với mỗi chỉ số ~i_k~ hãy cho biết giá trị của ~f(i_k)~.

Input

  • Dòng đầu chứa xâu ~s~;
  • Dòng thứ hai chứa số nguyên dương ~m~ và theo sau là ~m~ số nguyên dương ~i_k~, hai số liên tiếp cách nhau một dấu cách.

Giới hạn:

  • ~1 ≤ |s|, m ≤ 10^6; 1 ≤ i_k ≤ |s|~.

Output

  • Ghi trên một dòng các giá trị ~f(i_k)~, hai số liên tiếp được ghi cách nhau một dấu cách.

Sample

Input #1
zaaxbaacbaa
11 1 2 3 4 5 6 7 8 9 10 11
Output #1
0 1 2 0 0 1 3 0 0 1 11

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

Bình luận

Please read the guidelines before commenting.


  • 0
    congtyluuthaibao1978  đã bình luận lúc 28, Tháng 11, 2025, 4:41

    include <bits/stdc++.h>

    using namespace std;

    vector<int> zfunc(const string &s) { int n = s.size(); vector<int> z(n); int l = 0, r = 0; for (int i = 1; i < n; i++) { if (i <= r) z[i] = min(r - i + 1, z[i - l]); while (i + z[i] < n && s[z[i]] == s[i + z[i]]) z[i]++; if (i + z[i] - 1 > r) { l = i; r = i + z[i] - 1; } } return z; }

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

    string s;
cin >> s;
int n = s.size();

string t = s;
reverse(t.begin(), t.end());

string u = t + "#" + t;
vector<int> z = zfunc(u);

int m;
cin >> m;
while (m--) {
    int i;
    cin >> i;

    // vị trí tương ứng trong reversed string
    int pos = n + 1 + (n - i);

    cout << z[pos] << (m ? ' ' : '\n');
}
return 0;

    }