Tìm chuỗi dài nhất

[TeamSEOAQ]

Đề bài là tìm chuỗi lặp lại nhiều nhất trong chuỗi cho trước (độ dài tối thiểu là 2 ký tự).
vidụ:
Cho chuỗi: abcabccab
Kết quả xuất ra là : ab
Các huynh hướng dẫn dùm mình giải thuật và cho mình biết cần sử dụng hàm gì để giải quyết. Thanks!

View more random threads:

• chữa bài sắp xếp hòa nhập
• cần giúp về hàm getchar()
• Tìm cách tính cho vòng lặp. Mọi người giúp em!!!
• lỗi tính tổng mảng(MIPS)
• Lỗi khi In trong danh sách liên kết đơn
• Đinh thời chương trình trong C
• hàm nào trong thư viện string có chức năng loại bỏ từ giống nhau?
• chương trình tự tái sinh trong C
• hỏi hàm tính mủ trong C
• anh nào xem giúp e bài C++ này e làm co đúng ko

[baloenglish.2015]

Theo mình thì bạn cho kí tự đầu tiên trong chuổi chạy lần lượt đến cuối chuỗi (vừa chạy vừa so sánh) , nếu bằng nhau thì tăng lên 1 xong loại bỏ kí tự giống đó đi.
Xong Cho kí tự kế tiếp chạy như trên cho đến Null thì dừng.
Sau cùng chỉ việc so sánh chúng lại với nhau và xuất ra nó thôi!
Cách hơi tốn kém nhưng mình chỉ nghĩ ra có nhiêu đấy. Nếu ai có cách hay hơn thì mách dùm hì

[tungns]

Mình chưa hiểu lắm về giải thuật bạn nói. Với lại mình nghĩ nó không hữu dụng.
Có ai có cách gì thì mách mình với.

[admin]

Đề bài của bạn có vẻ không chặt chẽ lắm nhỉ . Mình giả sử s là chuỗi xuất hiện nhiều nhất và có độ dài lớn hơn 2 kí tự . Vậy dĩ nhiên các xâu con của s có độ dài 2 kí tự luôn có số lần xuất hiện lớn hơn hay bằng s trong xâu đã cho hay sao . --> Chỉ cần tìm xâu con có độ dài 2 xuất hiện nhiều nhất . Chỗ mình thắc mắc là ở đó bạn có thể nêu rõ đề lại và các test kết quả mà bạn có được không .
[IMG]images/smilies/icon_question.gif[/IMG]

[sangame]

Hix bạn cafelanh Dev C++ chỉ là IDE thôi không phải ngôn ngữ lập trình đâu . Còn các hàm tách và xử lí chuỗi được khai báo trong string.h của C bạn có thể đọc thêm . Ừm bạn tsandtm bạn không hiểu ý mình rồi ý mình là thế này :
vd1: ababcdfacbacbacb ==> acb (xuât hiện 3 lần) --> ac và cb cũng xuất hiện 3 lần vậy in ra thế nào
vd2: nfrixkacagagagbabcbcbc==>ag và bc (xuất hiện 3 lần)
vd3:abcabcadfhadfhadfhabcagabc==>abc (xuất hiện 4 lần). //Ở đầy cũng thế ab và bc cũng xuất hiện 4 lần
Đó các xâu con của acb (vd1) và abc (vd2) đều có số lần xuất hiện nhiều nhất --> in ra thế nào ??? Hay là tất cả các xâu ???? Hay là tìm xâu xuất hiện nhiều nhất có độ dài lớn nhất .
PS:Bạn cafelanh mình nghĩ bài này không đơn giản như ý cậu nói đâu cậu thử viết xem để mọi người tham khảo .

[minhthu1987]

ờ , tuy ko phải các huynh nhưng xin góp tí ti ý kiến vậy , trong devc++ mà mình đang học có hỗ trợ hàm tìm chuỗi này trong chuỗi kia và tách chuỗi lớn hơn thành chuỗi đã bỏ đi chuỗi nhỏ , bạn sử dụng hàm này cho đến khi chuỗi lớn có độ dài nhỏ hơn chuỗi nhỏ , nghĩa là 1 vòng for và 1 câu lệnh là xong , chúc may mắn

[toyota]

Mình làm 3 ví dụ sau là bạn hiểu liền
vd1: ababcdfacbacbacb ==> acb (xuât hiện 3 lần)
vd2: nfrixkacagagagbabcbcbc==>ag và bc (xuất hiện 3 lần)
vd3:abcabcadfhadfhadfhabcagabc==>abc (xuất hiện 4 lần).

cafelanh có thể cho mình biết hàm đó được không.
Nếu bài này trong pascal thì quá dễ. Nhưng trong C mình không biết sử dụng hàm của bạn nói.

[duongthidiu]

Ví dụ của mình là tìm xâu xuất hiện nhiều nhất và ưu tiên cho xâu có độ dài lớn nhất. trung_dk070384 Hiểu ý có thể hướng dẫn mình giải thuật được không.

[bevoll]

// bai toan tim ra string con co tan suat lon nhat trong 1 string
// bai toan tuong chung don gian nhung gom rat nhieu truong hop
// ta co the phan tich bai toan don gian nhu sau
/*
1 : nhap vao string can tim co ten la string a
2 : viet 1 function tim ra tan suat xuat hien cua string b(bat ki)trong string a
3 : voi phan tu dau tien cua string a
        tim tat ca cac string co 2 ki tu (gom co a12,a23,a34,....a(n-1)n)
        tim tat ca cac string co 3 ki tu (gom co a123 a234 ......a(n-2)(n-1)n)
        ....lap lai buoc nay cho den khi max of size string = n-i (truong hop i=0 nay chinh la string a)
4 : lap lai tuong tu buoc 3 voi cac phan tu thu 2 ,3 ,...n cua string a

5 : den day ta co the tim duoc tan suat cua tat ca cac string con
     va tim duoc tan suat lon nhat la maxcount
     
6 : cong viec con lai la viet ra cac string co cung tan suat lon nhat
    De lam duoc viec nay trong khi tim duoc string con ban luu vao 1 mang 2 chieu
    Vay viec viet ra cac phan tu co tan suat lon nhat don gian chi tim ra
    trong mang string,string nao xuan hien trong mang maxcount lan va viet ra

Phan tich bai toan da xong vay code chuong trinh khong con van de gi nua
*/

#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
// thu vien stdlib.h dung phuc vu cho viec cung cap bo nho cho mang Con tro
#define   max 20

// ham lengthString dung de kiem tra do dai cua 1 string
int lengthString (char a[max])
{
        int i=0;
        while (a[i]!='\0') {i++;}
        return  ( i );
        
}

//ham countString dung de kiem tra tan suat cua String con trong String goc
int countString(char a[max],char b[max],int size,int n)
{
    int j;
    int i=0,count=0,k=0;
    while(i<n-size)
    {
        for (j=0;j<size;j++){if(a[j]==b[j]) k++; }
        if(k==size) count++;
        k = 0;
        i++;
    }
    return (count);
}

//Chuong trinh chinh
int main ()
{
    int n,j,k,f;
    int i=0,size=2,soChuoiCon=0,maxcount=0;
    char a[max],*c[2000];
    printf("nhap vao chuoi can kiem tra :
");
    gets(a);
    n = lengthString(a);
    while(i<n) // bat dau voi phan tu dau tien cua day a
    {
        size = 2; //reset size doi voi phan tu tiep theo
	while(size<n-i)//bat dau tim tat ca cac chuoi con bat dau size =2 va maxsize = n-i
             {
               for(k=i;k<(n-size);k++)
                  {
		   c[soChuoiCon] = (char*)malloc((size+1) * sizeof(char));//cung cap bo nho cho con tro
		   for(j=0;j<size;j++)//luu chuoi con vao 1 con tro
               		{                		
                		*(c[soChuoiCon]+j)=a[k+j];
                		f = countString(a,c[soChuoiCon],size,n);
             			if(maxcount<=f){maxcount=f;}//tan so xuat hien nhieu nhat
               		}
		    printf("
%s\t %d lan",c[soChuoiCon],f);
             	    soChuoiCon++;
            	   }
           	size++;
              }
        i++;
       
    }
    // In ket qua ra man hinh
    k=0;
    for(i=0;i<soChuoiCon;i++) //tim trong mang con tro phan tu co tan so cao nhat va in ra man hinh
    {
        for(j=i+1;j<n;j++){if(c[i]==c[j]) k++;}
        if(k==maxcount) printf("%s
",c[i]);
        k=0;
    }
    getch();
}

đến đây còn 1 vấn đề mình vẫn chưa hiểu
vd chuỗi dài nhât của mình là ab chẳng hạn sau khi chạy chương trình sẽ hiện thêm 1 kí tự lạ vd là ab^ hoặc ab) mỗi chuỗi in ra đều thêm 1 kí tự lạ trong bảng mã ANCII

theo mình nghĩ chắc việc sử dụng mảng con trỏ có vấn đề !!! bạn nào biết comment dùm nha

[machao112]

Giải thuật bạn đúng rùi. Mình đã hiểu. Nhưng cho minh hỏi một tí:
c[soChuoiCon] = (char*)malloc((size+1) * sizeof(char));
Cho mình hỏi malloc là sao? Mình chưa biết cái này.
Với lại hàm lengstring của bạn có thể dùng hàm strlen trong thư viện string.h để thay thế được không.