/*  Copyright (C) 2008 Joshua Judson Rosen <rozzin@geekspace.com>.

    This program is free software: you can redistribute it and/or
    modify it under the terms of the GNU General Public License
    version 3 as published by the Free Software Foundation.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with this program; see the file COPYING. If not, see
    <http://www.gnu.org/licenses/> or write to:

        The Free Software Foundation, inc.
        51 Franklin Street, Fifth Floor
        Boston, MA 02110-1301
        USA
*/

#include <stdlib.h>
#include <string.h>
#include <glib.h>
#include "util.h"

char *
best_common_substr (const char *string1, const char *string2,
             int *substr_pos1_out, int *substr_pos2_out, double *score_out)
{
  int string1_len = strlen(string1), string2_len = strlen(string2);
  int *sslengths = g_new0 (int, (string1_len+1) * (string2_len+1));

  char *lcs = NULL;
  int lcs_len = 0;
  int best_string1_pos = 0;
  int best_string2_pos = 0;
  double best_score = 0;

  int string1_pos, string2_pos;

  for (string1_pos=1; string1_pos <= string1_len; string1_pos++) {
    for (string2_pos=1; string2_pos <= string2_len; string2_pos++) {
      int idx = string1_pos*string2_len + string2_pos;

      if (string1[string1_pos-1] == string2[string2_pos-1]) {
        double score;
        int substr_len;

        sslengths[idx] = sslengths[idx-string2_len-1] + 1;

        substr_len = sslengths[idx];
          /* weight matches near the beginning of both strings more heavily: */
        score = pow (1 - ((double) (string1_pos - substr_len) / string1_len), 2)
              * pow (1 - ((double) (string2_pos - substr_len) / string2_len), 2)
              * substr_len;

        if (score > best_score) {
          lcs_len = sslengths[idx];
          best_score = score;
          best_string1_pos = string1_pos - lcs_len;
          best_string2_pos = string2_pos - lcs_len;
        }
      }
    }
  }

  g_free (sslengths);

  if (lcs_len > 0) {
    lcs = g_strndup (string1 + best_string1_pos, lcs_len);
  }

  if (substr_pos1_out) {
    *substr_pos1_out = best_string1_pos;
  }
  if (substr_pos2_out) {
    *substr_pos2_out = best_string2_pos;
  }
  if (score_out) {
    *score_out = best_score;
  }

  return lcs;
}