Trang 1 trên tổng số 2 12 Cuối cùngCuối cùng
Từ 1 tới 10 trên tổng số 13 kết quả

Đề tài: Xác định chuỗi overlap trong C++ thế nào

  1. #1
    Ngày gia nhập
    10 2011
    Bài viết
    10

    Unhappy Xác định chuỗi overlap trong C++ thế nào

    ta có 2 chuỗi:
    A:abcdjgk
    B:kfngkgabcd
    thì "abcd" là chuỗi overlap vì nó là tiền tố của chuỗi A và là hậu tố của chuỗi B

    mọi ngừơi giúp mình xác định độ dài chuỗi ovelap với.như vidu trên thì kết quả sẽ là 4

  2. #2
    Ngày gia nhập
    04 2010
    Bài viết
    1,534

    Giải thích cho biết tại sao là 4 rồi người ta sẽ dùng lời giải thích trên chuyển thành thuật toán cho.

    Lưu ý là giải thích càng cặn kẽ thì thuật toán càng dễ hiểu. Giải thích đúng trình tự thì thuật toán có thể dịch thẳng ra code.

  3. #3
    Ngày gia nhập
    01 2011
    Nơi ở
    /dev/null
    Bài viết
    6

    Xài for loop và check Position lần lượt từ kí tự đầu của A trong B, nếu 1 kí tự của A có trong B thì Break lần loop đó là + thêm một kí tự và cứ check dần như thế thui. Thuật toán này ko khó mà bạn.
    NOTHING

  4. #4
    Ngày gia nhập
    10 2011
    Bài viết
    10

    Trích dẫn Nguyên bản được gửi bởi vic4key Xem bài viết
    Xài for loop và check Position lần lượt từ kí tự đầu của A trong B, nếu 1 kí tự của A có trong B thì Break lần loop đó là + thêm một kí tự và cứ check dần như thế thui. Thuật toán này ko khó mà bạn.
    Nhưng còn cách kiểm tra cái chuỗi ở cuối thì sao bạn..vidu như trên thì sao biết 'abcd' ở cuối chuỗi B để mình break ra nhỉ?
    để mình thử 2 vòng for thế nào.tks c nhé

  5. #5
    Ngày gia nhập
    11 2010
    Bài viết
    589

    Với bài này có thể áp dụng thuật toán KMP, thêm một chút chỉnh sửa
    http://diendan.congdongcviet.com/showthread.php?t=51906
    Giả sử |A| = m, |B| = n
    Thay vì tìm chuỗi A trong chuỗi B, nếu n>=m ta so sánh A[0:m-1] với B[0:n-1], còn không so sánh với B[m-n:n-1]. So cho đến kết thúc chuỗi B thì thôi. Giá trị của con trỏ của chuỗi A sau vòng lặp chính là độ dài đoạn overlap:
    Python Code:
    1. def overlap_len(B, A):
    2.     map = compute_KMP_map(A)
    3.     i = 0
    4.     j = 0
    5.     n = len(B); m = len(A)
    6.     if n < m: j = m-n
    7.     while(j < n):
    8.         while ( (i >= 0) and (B[j] != A[i]) ):
    9.             i = map[i]
    10.         i = i+1
    11.         j = j+1
    12.     return i
    Đã được chỉnh sửa lần cuối bởi boss14420 : 07-04-2012 lúc 04:18 PM.

  6. #6
    Ngày gia nhập
    07 2011
    Nơi ở
    hà nội
    Bài viết
    11

    Mặc định Xác định chuỗi overlap trong C++ thế nào

    Day la bai cua minh:
    Attached Files Attached Files

  7. #7
    Ngày gia nhập
    11 2010
    Bài viết
    589

    Trích dẫn Nguyên bản được gửi bởi vinh.kids1992 Xem bài viết
    Day la bai cua minh:
    Nếu lấy s1 = dhgababchdababc, s2 = ababchjfjd thì bài của bạn ra kết quả là 6, trong khi phần overlap chỉ dài có 5.

  8. #8
    Ngày gia nhập
    07 2011
    Nơi ở
    hà nội
    Bài viết
    11

    Mặc định Cam on cau nhieu nha!!!

    Trích dẫn Nguyên bản được gửi bởi boss14420 Xem bài viết
    Nếu lấy s1 = dhgababchdababc, s2 = ababchjfjd thì bài của bạn ra kết quả là 6, trong khi phần overlap chỉ dài có 5.
    Day minh code lai roi.
    Code:
    #include <iostream>
    
    using namespace std;
    
    #include <string.h>
    
    int overlap(char *, char *);
    
    main()
    {
    	char *s1, *s2;
    	s1 = new char[80];
    	s2 = new char[80];
    	cin.getline(s1, 80);
    	cin.getline(s2, 80);
    	cout << overlap(s1, s2) << endl;
    	delete s1;
    	delete s2;
    	system("PAUSE");
    }
    
    int overlap(char *s1, char *s2){
    	int k = 0, j = 0, dem1 = 0, dem2 = 0;
    	for(int i = 0; s2[i] != '\0'; i++){
    		if(s2[i] == s1[k]){
    			dem1++;
    			k++;
    		}
    		else{
    		    dem1 = 0;
    		    k = 0;
    		}
    	}
    	for(int i = 0; s1[i] != '\0'; i++){
    		if(s1[i] == s2[j]){
    			dem2++;
    			j++;
    		}
    		else{
    			dem2 = 0;
    			j = 0;
    		}
    	}
    	if(dem1 > dem2) return dem1;
    	else return dem2;
    }

  9. #9
    Ngày gia nhập
    11 2010
    Bài viết
    589

    Vẫn sai
    Code:
    boss14420 /media/DOCUMENT/code_exp/cpp_example $ ./overlap2 
    agfjhdababccd
    cdahs
    0

  10. #10
    Ngày gia nhập
    07 2011
    Nơi ở
    hà nội
    Bài viết
    11

    Trích dẫn Nguyên bản được gửi bởi boss14420 Xem bài viết
    Vẫn sai
    Code:
    boss14420 /media/DOCUMENT/code_exp/cpp_example $ ./overlap2 
    agfjhdababccd
    cdahs
    0
    Bạn tìm lỗi giỏi quá. Với trường hợp này mình nghĩ mãi mới ra
    Code:
    int overlap(char *s1, char *s2){
    	int i = 0, k = 0, j = 0, dem1 = 0, dem2 = 0;
    	for(i = 0; s2[i] != '\0'; i++){
    		if(s2[i] == s1[k]){
    			dem1++;
    			k++;
    		}
    		else{
    			if(dem1){
    		    	dem1 = 0;
    		    	k = 0;
    		    	i--;
    			}
    			else{
    				dem1 = 0;
    				k = 0;
    			}
    		}
    	}
    	for(i = 0; s1[i] != '\0'; i++){
    		if(s1[i] == s2[j]){
    			dem2++;
    			j++;
    		}
    		else{
    			if(dem2){
    		    	dem2 = 0;
    		    	j = 0;
    		    	i--;
    			}
    			else{
    				dem2 = 0;
    				j = 0;
    			}
    		}
    	}
    	if(dem1 > dem2) return dem1;
    	else return dem2;
    }

Các đề tài tương tự

  1. Lập trình C Thay thế chuỗi s1 trong chuỗi s bằng chuỗi s
    Gửi bởi duytue trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 7
    Bài viết cuối: 23-09-2011, 04:16 PM
  2. thay thế chuỗi con thứ i trong chuỗi mẹ bằng 1 chuỗi khác
    Gửi bởi nhat1811 trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 3
    Bài viết cuối: 06-08-2011, 08:25 AM
  3. Hirrent boot Partitions overlap
    Gửi bởi cSharp trong diễn đàn Thắc mắc chung
    Trả lời: 0
    Bài viết cuối: 17-07-2010, 11:19 PM
  4. Nhập chuỗi, đếm số lần xuất hiện các từ trong chuỗi như thế nào?
    Gửi bởi VizDee trong diễn đàn Nhập môn lập trình C/C++
    Trả lời: 7
    Bài viết cuối: 23-01-2010, 01:33 PM
  5. Tách chuỗi số giảm dần trong một chuỗi lớn, thuật toán xử lý như thế nào?
    Gửi bởi longtom trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 12
    Bài viết cuối: 12-05-2009, 04:10 PM

Quyền hạn của bạn

  • Bạn không thể gửi đề tài mới
  • Bạn không thể gửi bài trả lời
  • Bạn không thể gửi các đính kèm
  • Bạn không thể chỉnh sửa bài viết của bạn