| 745 | */ |
| 746 | protected: |
| 747 | static ssize_t diff_commonOverlap(const string_t &text1, const string_t &text2) { |
| 748 | // Cache the text lengths to prevent multiple calls. |
| 749 | const ssize_t text1_length = text1.length(); |
| 750 | const ssize_t text2_length = text2.length(); |
| 751 | // Eliminate the null case. |
| 752 | if (text1_length == 0 || text2_length == 0) { |
| 753 | return 0; |
| 754 | } |
| 755 | // Truncate the longer string. |
| 756 | string_t text1_trunc = text1; |
| 757 | string_t text2_trunc = text2; |
| 758 | if (text1_length > text2_length) { |
| 759 | text1_trunc = right(text1, text2_length); |
| 760 | } else if (text1_length < text2_length) { |
| 761 | text2_trunc = text2.substr(0, text1_length); |
| 762 | } |
| 763 | const ssize_t text_length = std::min(text1_length, text2_length); |
| 764 | // Quick check for the worst case. |
| 765 | if (text1_trunc == text2_trunc) { |
| 766 | return text_length; |
| 767 | } |
| 768 | |
| 769 | // Start by looking for a single character match |
| 770 | // and increase length until no match is found. |
| 771 | // Performance analysis: http://neil.fraser.name/news/2010/11/04/ |
| 772 | ssize_t best = 0; |
| 773 | ssize_t length = 1; |
| 774 | while (true) { |
| 775 | string_t pattern = right(text1_trunc, length); |
| 776 | size_t found = text2_trunc.find(pattern); |
| 777 | if (found == string_t::npos) { |
| 778 | return best; |
| 779 | } |
| 780 | length += found; |
| 781 | if (found == 0 || right(text1_trunc, length) == text2_trunc.substr(0, length)) { |
| 782 | best = length; |
| 783 | length++; |
| 784 | } |
| 785 | } |
| 786 | } |
| 787 | |
| 788 | /** |
| 789 | * Do the two texts share a substring which is at least half the length of |