Nén xâu

View as PDF
All submissions
Best submissions
Read editorial
Time limit:
Scratch 5.0s
Author:
admin
Problem type
Points: 100 (p) Time limit: 1.0s Memory limit: 256M Input: stdin Output: stdout

Một xâu ký tự có thể nén lại thành một xâu mới bằng cách nén các ký tự giống nhau đứng cạnh nhau. Ví dụ trong xâu \(aaaa\) sẽ nén thành \(4a\). Hãy lập trình để nén một xâu ký tự thường theo cách trên.

Input

  • Một xâu các ký tự là chữ cái thường có tối đa \(10^5\) ký tự.

Output

  • Một xâu ký tự sau khi nén.

Example

Test 1

Input 
mmaabbbeeeezh
Output 
2m2a3b4ezh

Comments


  • 0
    KTGAME    5:57 p.m. 20 aug, 2024 
    Gợi ý nếu bạn thực sự không hiểu:

Ta duy trì 1 biến i tại vị trí bên trái
sau đo duyệt while i < số kí tự (len hoặc size)
ta sẽ để 1 biến j = i+1 tức là lấy 1 phần tử về bên phải
đoạn duyệt kí tự
thêm 1 vòng lặp con while khi j<= len hoặc size và xau[j]==xau[i] hoặc xau[j-1] đều như nhau: j+=1

sau đó sử lý số ta chỉ cần ghi vào j-i nhưng vì số 1 sẽ không ghi nên ta xử lý trường hợp này
đặt biến x = '' (rỗng)
nếu j-i != 1 thì x = j-i (chuyển về string nhé)

xau_result += x + xau[i]

Thuật 2 con trỏ với O(N)

    • 0
      SBD20_Caominhduc    10:26 a.m. 4 aug, 2024 

      #include <bits/stdc++.h>
using namespace std;
string st;
int n;
int main()
{
    cin >> st;
    n=st.size();
    int cc=1;
    for(int i=0;i<n;i++)
    {
        if(st[i]==st[i+1])
        {
            cc++;
        }else
        {
            if(cc!=1)cout << cc << st[i];
            else cout << st[i];
            cc=1;
        }
    }
    return 0;
}

      Code C++ cho ai cần

      Spoiler

      Ngoại trừ: SBD12_LamLDK; NamHackerLord5511; SBD11_TOANTHITRAN

      1 reply

      • -3
        baothanh2010    9:21 a.m. 6 jun, 2024

        include <bits/stdc++.h>

        using namespace std;
        string s;
        string s1="";
        long long d;
        int main()
        {
        cin>>s;
        for(int i=0;i<s.size();i++)
        {
        d=0;
        if(s[i-1]==s[i])
        {
        d++;
        while(s[i-1]==s[i])
        {
        d++;
        i++;
        }
        s1=s1+to_string(d)+s[i-1];
        }
        if(s[i-1]!=s[i]&&s[i]!=s[i+1])
        s1=s1+s[i];
        }
        cout<<s1;
        return 0;
        }


        • 0
          PY1F04_phan_nhat_binh    10:52 a.m. 3 may, 2024

          cho minh xin hint python cua bai nay di


          • -3
            xthabao1    7:57 p.m. 30 sep, 2023

            test sai hay sao ái


            • 0
              khanhhunghack    7:56 a.m. 10 jan, 2022

              làm phiền daicadihoc tăng time cho scratch ạ.

              1 reply

              • -46
                thanhyl7a20    4:26 p.m. 12 oct, 2021

                This comment is hidden due to too much negative feedback. Click here to view it.

                3 replies

                • 17
                  SPyofgame    7:10 p.m. 6 jun, 2020 ← edit 5

                  Spoiler Alert

                  Hint 1

                  Duyệt qua xâu, và đếm số lượng kí tự bằng nhau liền nhau.

                  Xuất kết quả và chuyển sang kí tự tiếp theo

                  Notice

                  Cẩn thận trường hợp chỉ có một kí tự đơn lẻ

                  Reference AC code | O(n) time | O(1) auxiliary space | Online Solving

                  C++
                  for (char c = getchar(), p = c; c != EOF; p = c)
{
    int cnt = 0;
    while (p == c) cnt++, c = getchar();
    if (cnt > 1) cout << cnt;
    cout << p;
}