Hỏi ý tưởng bài tập về đếm xâu ký tự

[ducdtm (Đức Lê)]

Mọi người cho em xin ý tưởng bài này với ạ, em làm bị sai test 2 và em cảm thấy thuật toán của em ko đc chuẩn ạ!

Đề bài: http://laptrinhphothong.vn/Problem/Details/5870

#include <bits/stdc++.h>
using namespace std;
string s;
int dem = 0, tmp;
int main()
{
    cin>>s;
    for(int i=0;i<s.size()-1;i++)
    {
        for(int j=i+1;j<s.size();j++)
        {
            tmp =0;
            for(int z=i;z<=j;z++)
            {
                if(s[z]==s[z+1]) tmp++;
            }
            if(tmp==0) dem++;
        }

    }
    cout<<dem;
}

[ducdtm (Đức Lê)]

a giải thích giúp e đc ko ạ, đọc cái link đó e thấy hơi trừu tượng ạ

[Sena (Sena Alaire)]

Bài này em nghĩ là quay lui, ý tưởng của em là như thế này:
Mình sẽ sinh ra các xâu, rồi cho qua hàm kiểm tra xem trong xâu đó có 2 xâu con liên tiếp trùng nhau hay không. Sau đó đặt biến đếm, với mỗi xâu thỏa mãn thì tăng biến đếm.

[rogp10]

Đọc từ từ nhé https://tryalgo.org/en/strings/2021/02/15/count-distinct-substrings/
O(n\log^2 n)

[ducdtm (Đức Lê)]

e đã giải đc rồi ạ, cảm ơn mọi người!