2010-01-29 40 views
5

Tôi đã dành nhiều ngày làm việc trên một hàm để nhận các ký tự thông thường trong một chuỗi các chuỗi, theo thứ tự đúng, để tạo một ký tự đại diện.Tìm các ký tự chung trong chuỗi các chuỗi, theo đúng thứ tự

Dưới đây là ví dụ để giải thích sự cố của tôi. Tôi đã thực hiện khoảng 3 chức năng, nhưng tôi luôn luôn có một lỗi khi vị trí tuyệt đối của mỗi chữ cái là khác nhau.

Giả sử "+" là "char ký tự đại diện":

Array(
0 => '48ca135e0$5', 
1 => 'b8ca136a0$5', 
2 => 'c48ca13730$5', 
3 => '48ca137a0$5'); 

nên trở lại:

$wildcard='+8ca13+0$5'; 

Trong ví dụ này, điều khó khăn là $array[2] như 1 char hơn những người khác.

dụ khác:

Array(
0 => "case1b25.occHH&FmM", 
1 => "case11b25.occHH&FmM", 
2 => "case12b25.occHH&FmM", 
3 => "case20b25.occHH&FmM1"); 

nên trở lại:

$wildcard='case+b25.occHH&FmM+'; 

Trong ví dụ này, các bộ phận phức tạp là:
- chars Lặp đi lặp lại, chẳng hạn như 1 -> 11 trong "để xóa "một phần, và c -> cc trong phần chung
-" 2 "char trong mảng $ [2] & [3] trong phần" để xóa "không ở cùng vị trí
- "1" char ở cuối chuỗi cuối

Tôi thực sự cần trợ giúp vì tôi không thể tìm thấy giải pháp cho chức năng này và nó là một phần chính của ứng dụng của tôi.

Xin cảm ơn trước, đừng ngần ngại đặt câu hỏi, tôi sẽ trả lời nhanh nhất có thể.

Mykeul

+0

Nó sẽ không giết bạn, vì vậy không cần phải hét to như vậy ;-) – raoulsson

+0

Hum OK ... đó là phần chỉnh sửa trên "HEEELLPPP" :) ... Nó sẽ không giết tôi, có, nhưng tôi thực sự, thực sự, cần phải làm cho nó hoạt động ... – Mykeul

+0

Rất vui khi bạn thay đổi nó! Thật tuyệt vời khi đọc ngay bây giờ :-) – raoulsson

Trả lời

2

mã chính:
Bước 1: Sắp xếp chuỗi theo độ dài, ngắn nhất để dài nhất, vào mảng []
Bước 2: So sánh chuỗi trong mảng [0] và mảng [1] để nhận được $ temp_wildcard
bước 3: so sánh chuỗi trong mảng [2] với $ temp_wildcard để tạo ra $ mới temp_wildcard
bước 4: tiếp tục so sánh mỗi chuỗi với $ temp_wildcard - các $ cuối cùng wildcard là bạn $ temp_wildcard

OK, vì vậy bây giờ chúng tôi xuống đến vấn đề làm thế nào để so sánh hai chuỗi để trả về chuỗi ký tự đại diện của bạn.

Mã chương trình con: So sánh các ký tự theo từng ký tự, thay thế các ký tự đại diện thành giá trị trả về của bạn khi so sánh không khớp.

Để xử lý vấn đề có độ dài khác nhau, hãy chạy so sánh này thêm một thời gian cho mỗi ký tự mà chuỗi thứ hai dài hơn với độ lệch. (So ​​sánh string1 [x] với chuỗi2 [x + offset].) Đối với mỗi chuỗi được trả về, hãy đếm số ký tự đại diện. Chương trình con sẽ trả về câu trả lời với số ký tự đại diện ít nhất.

Chúc may mắn!

+0

Xin chào và cảm ơn vì sự chờ đợi của bạn! Đó là một algorythm tốt và tôi sẽ thử nó tối nay tôi nghĩ. Vẫn còn 1 trường hợp tôi không thể khớp: Array ("abcd", "bcde"); => cùng độ dài nhưng tôi sẽ nhận được "+ bcd +". Nó vẫn là một algorythm rất tốt, tốt hơn so với tôi. Mykeul – Mykeul

3

Dường như bạn muốn tạo thứ gì đó giống như cụm từ thông dụng trong số các chuỗi ví dụ. Điều này có thể khá phức tạp. Tìm thấy liên kết này, không chắc chắn nếu nó có liên quan: http://scholar.google.com/scholar?hl=en&rlz=1B3GGGL_enEE351EE351&q=%22regular%20expression%20by%20example%22&oq=&um=1&ie=UTF-8&sa=N&tab=ws

Mặt khác, nếu bạn chỉ cần một ký tự đại diện cụ thể có nghĩa là "0 hoặc nhiều ký tự", sau đó nó sẽ được dễ dàng hơn nhiều. Thuật toán Levenshtein distance tính toán sự giống nhau giữa 2 chuỗi. Thông thường chỉ có kết quả là cần thiết, nhưng trong trường hợp của bạn những nơi khác biệt là quan trọng. Bạn cũng cần phải thích nghi điều này cho N chuỗi. Vì vậy, tôi khuyên bạn nên nghiên cứu thuật toán này và hy vọng bạn sẽ nhận được một số ý tưởng làm thế nào để giải quyết vấn đề của bạn (ít nhất bạn sẽ nhận được một số thực hành với các thuật toán văn bản và lập trình năng động).

thuật toán Heres trong PHP: _http: //en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Levenshtein_distance#PHP

Bạn có thể muốn cũng để tìm kiếm việc triển khai PHP "diff". http://paulbutler.org/archives/a-simple-diff-algorithm-in-php/

+0

Xin chào, Cảm ơn bạn đã rất tiếc, tuy nhiên: - Tôi không nghĩ mình có thể sử dụng regex vì tôi không biết loại ký tự trong chuỗi, không phải kiểu ký tự od mà tôi sẽ phải xóa - Tôi đọc về khoảng cách Levenshtein nhưng nó cho biết "số khác biệt", không khác biệt là gì ... và không có thứ tự. - Liên kết cuối cùng hiển thị liên kết tải xuống tệp PHP không hoạt động nữa và nhận xét chỉ cung cấp các phần của tập lệnh. Tôi thực sự cần giữ các ký tự thông thường và thứ tự. – Mykeul

Các vấn đề liên quan