Code đếm số cặp xâu tương đương bị Time Limit Exceeded

[Duc_Khai_Tong (da sun kid)]

Chào mọi người. Mình/em có bài tập như này. Cho một xâu độ dài không quá 100. đếm xem xâu đó có bao nhiêu cặp xâu con tương đương (2 xâu tương đương là 2 hoán vị kí tự của nhau).
Mình có ý tưởng thế này. Nhưng case phức tạp thì bị time limit exceeded. Dùng cách sort cũng k ổn :((. Giúp mình/em tối ưu đoạn code với.

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
bool similar(string a, string b)
{
    int n=a.length(), flag=0;
    char str[26]; int A[26]={0}; int B[26]={0};
    for(int i=97; i<123; i++) 
    {
        str[i-97]=i;
    }
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<26; j++)
        {
            if(a[i]==str[j]) A[j]++;
            if(b[i]==str[j]) B[j]++;
        }
    }
    for(int i=0; i<26; i++)
        if(A[i]!=B[i])  flag=1;
    if(flag==0) return true;
    if(flag==1) return false;
}
int count(string s)
{
    int n=s.length(); int count=0;
    for(int k=1; k<n; k++)
    {
        for(int i=0; i<n-k+1; i++)
        {
        for(int j=i+1; j<n-k+1; j++)
        if(similar(s.substr(i, k), s.substr(j, k))) count++;
        }
    }
    return count;
}
int main()
{
   int n; cin >> n;
   char a[100];
   while(n>0)
   {
      scanf("%s", a);
      printf("%i", count(a));
      printf("\n");
      n--;
   }
   return 0;
}

[hungaya (Hung)]

Bạn cho thêm ví dụ về 2 xâu tương đương nhé.
Thêm test case mà bạn bị “time limit exceeded” luôn.

[Duc_Khai_Tong (da sun kid)]

[Duc_Khai_Tong (da sun kid)]

Dòng đầu là số test case

[rogp10]

Nhầm, O(n^3*(n+k)) theo brute force (số xâu con độ dài k ^ 2/2 * tính bảng tần suất * độ dài xâu), nhưng hằng số quá cao nên tèo vì vậy bỏ cái vòng lặp j < 26 là đúng.

Ý tưởng của bảng tần suất là ntn: Để đếm dễ dàng, thay vì viết nguyên số, ta sẽ gạch một dấu gạch để tăng lên 1 (cứ 5 gạch thì gạch thứ 5 là gạch chéo). Với một bảng 26 ô a…z, cứ gặp chữ nào ta thêm 1 gạch vào ô tương ứng với chữ ấy. Nói cách khác, count[A[i] - 'a']++;.

• Rolling “count”: (tính bảng tần suất 1 lần + Số xâu con độ dài k * |bảng chữ cái|) * độ dài = O(n^2*m).
• Rolling hash: (tính bảng tần suất 1 lần + |bảng chữ cái| + số xâu con) * độ dài = O((n+m)*n).

[Van_An2 (Văn An)]

#include <bits/stdc++.h>

using namespace std;

int count_a[35], count_b[35];

int calc(string s)
{
    int res = 0;
    for( int index_1 = 0; s[index_1] != '\0'; index_1++) {
        for( int index_2 = index_1 + 1; s[index_2] != '\0'; index_2++) {
            for( char i = 'a'; i <= 'z'; i++) count_a[ i - 'a'] = count_b[ i - 'a'] = 0;
            for( int k = 0; s[index_1 + k] != '\0' && s[index_2 + k] != '\0'; k++) {
                count_a[ s[index_1 + k] - 'a']++;
                count_b[ s[index_2 + k] - 'a']++;
                // check 
                bool check = true;
                for( char i = 'a'; i <= 'z'; i++) if( count_a[ i - 'a'] != count_b[ i - 'a']) {
                    check = false;
                    break;
                }
                if( check) res ++;
            }
        }
    }
    return res;
}

int main(){
    int n;
    cin >> n;
    while( n--) {
        string s;
        cin >> s;
        cout << calc(s) << endl;
    }
}

this code for you

[noname00 (HK boy)]

for( int index_1 = 0; s[index_1] != ‘\0’; index_1++)

Tại sao không phải là

for (int index_1 = 0; index_1 < s.size(); index_1++)

nhỉ

P/s: Lưu ý cách đóng mở ngoặc: sau mở ngoặc (, [ không có dấu cách.

Code của bạn là O(n^3 * 26^2), n <= 100, chưa kể xử lí nhiều test nên chắc chắn TLE.

[dnam257 (Nguyen Dang Nam)]

Code này của bạn chỉ đúng với xâu có kí tự trong trỏng từ a-z thôi . Mà hình như bạn cũng học UET đúng không ?? Có thể cho mình xin thông tin cùng trao đổi không ?