From bff179888f6d247c3584150f0c729634b95c745b Mon Sep 17 00:00:00 2001 From: zufuliu Date: Sat, 13 Jan 2018 17:12:57 +0800 Subject: [PATCH] Improve similar_text(), reduce recursive call to php_similar_char() If the longest common substring is the leftmost common substring, there is no need to check the string prefixes for further common substrings, since there are none. --- ext/standard/string.c | 10 ++++++---- 1 file changed, 6 insertions(+), 4 deletions(-) diff --git a/ext/standard/string.c b/ext/standard/string.c index 42e58ca498..12e91dc112 100644 --- a/ext/standard/string.c +++ b/ext/standard/string.c @@ -3557,7 +3557,7 @@ PHP_FUNCTION(strrev) /* {{{ php_similar_str */ -static void php_similar_str(const char *txt1, size_t len1, const char *txt2, size_t len2, size_t *pos1, size_t *pos2, size_t *max) +static void php_similar_str(const char *txt1, size_t len1, const char *txt2, size_t len2, size_t *pos1, size_t *pos2, size_t *max, size_t *count) { char *p, *q; char *end1 = (char *) txt1 + len1; @@ -3565,11 +3565,13 @@ static void php_similar_str(const char *txt1, size_t len1, const char *txt2, siz size_t l; *max = 0; + *count = 0; for (p = (char *) txt1; p < end1; p++) { for (q = (char *) txt2; q < end2; q++) { for (l = 0; (p + l < end1) && (q + l < end2) && (p[l] == q[l]); l++); if (l > *max) { *max = l; + *count += 1; *pos1 = p - txt1; *pos2 = q - txt2; } @@ -3583,11 +3585,11 @@ static void php_similar_str(const char *txt1, size_t len1, const char *txt2, siz static size_t php_similar_char(const char *txt1, size_t len1, const char *txt2, size_t len2) { size_t sum; - size_t pos1 = 0, pos2 = 0, max; + size_t pos1 = 0, pos2 = 0, max, count; - php_similar_str(txt1, len1, txt2, len2, &pos1, &pos2, &max); + php_similar_str(txt1, len1, txt2, len2, &pos1, &pos2, &max, &count); if ((sum = max)) { - if (pos1 && pos2) { + if (pos1 && pos2 && count > 1) { sum += php_similar_char(txt1, pos1, txt2, pos2); } -- 2.40.0