3个字符串最大公共子字符串

 

3个字符串的最大公共子字符串。

用了动态规划算法。（二维和三维的）

#include <iostream>
#include <string>
#include <vector>
#include <map>

using namespace std;


void equal_sub_str(const char *str1, const char *str2, map<string, int> &coll)
{
  coll.clear();

  int len1 = strlen(str1);
  int len2 = strlen(str2);

  int **arr = new int*[len2 + 1];
  for (int i=0; i<len2+1; i++)
  {
    arr[i] = new int[len1 + 1];
  }

  for (int i=1; i<len2+1; i++)
  {
    for (int j=1; j<len1+1; j++)
    {
      if (str1[j-1] == str2[i-1])
      {
        arr[i][j] = arr[i-1][j-1] + 1;
      }
    }
  }

  /*
  cout << "\t\t";
  for (int i=0; i  {
    cout << str1[i] << "\t";
  }
  cout << endl;
  for (int i=0; i  {
    if (i == 0)
    {
      cout << "\t";
    }
    else
    {
      cout << str2[i-1] << "\t";
    }

    for (int j=0; j    {
      cout << arr[i][j] << "\t";
    }
    cout << endl;
  }
  cout << endl;
  cout << "--------------------------------------------" << endl;
  */


  for (int i=1; i<len2+1; i++)
  {
    for (int j=1; j<len1+1; j++)
    {
      int sub_str_len = arr[i][j];
      if (sub_str_len > 0)
      {
         cout << "i = " << i << " --- j = " << j << endl;
         string sub_str(str1+j-sub_str_len, str1+j);
         cout << "sub_str = " << sub_str << endl;
         coll[sub_str] = 0;
      }
    }
  }

  return;
}

void max_sub_str(const char *str1, const char *str2, const char *str3)
{
  map<string, int> coll1;
  equal_sub_str(str1, str2, coll1);

  cout << "equal: " << str1 << " --- " << str2 << endl;
  map<string, int>::const_iterator pos;
  for (pos = coll1.begin();
       pos != coll1.end();
       ++pos)
  {
    cout << pos->first << endl;
  }

  map<string, int> coll2;
  equal_sub_str(str2, str3, coll2);

  cout << "equal: " << str2 << " --- " << str3 << endl;
  for (pos = coll2.begin();
       pos != coll2.end();
       ++pos)
  {
    cout << pos->first << endl;
  }
//----------------------------------------------------------------------

  map<string, int> res;
  for (pos = coll1.begin();
       pos != coll1.end();
       ++pos)
  {
    const string &key = pos->first;
    if (res.find(key) == res.end())
    {
      res[key] = 1;
    }
    else
    {
      res[key]++;
    }
  }
  for (pos = coll2.begin();
       pos != coll2.end();
       ++pos)
  {
    const string &key = pos->first;
    if (res.find(key) == res.end())
    {
      res[key] = 1;
    }
    else
    {
      res[key]++;
    }
  }
  for (pos = res.begin();
       pos != res.end();
       ++pos)
  {
    if (pos->second == 2)
    {
      cout << "common = " << pos->first << endl;
    }
  }

  return;
}



void max_sub_str_new(const char *str1, const char *str2, const char *str3)
{
  int len1 = strlen(str1);
  int len2 = strlen(str2);
  int len3 = strlen(str3);

  int ***arr = new int**[len3 + 1];
  for (int i=0; i<len3+1; i++)
  {
    arr[i] = new int*[len2+1];
    for (int j=0; j<len2+1; j++)
    {
      arr[i][j] = new int[len1 + 1];
      for (int k=0; k<len1+1; k++)
      {
        cout << "*** " << arr[i][j][k] << endl;
      }
      //memset(arr[i][j], 0, sizeof(int)*(len1+1));

    }
  }

  for (int i=1; i<len3+1; i++)
  {
    for (int j=1; j<len2+1; j++)
    {
      for (int k=1; k<len1+1; k++)
      {
        if (str1[k-1] == str2[j-1] && str1[k-1] == str3[i-1])
        {
          arr[i][j][k] = arr[i-1][j-1][k-1] + 1;
        }
      }
    }
  }

  for (int i=1; i<len3+1; i++)
  {
    for (int j=1; j<len2+1; j++)
    {
      for (int k=1; k<len1+1; k++)
      {
        int sub_str_len = arr[i][j][k];
        if (sub_str_len > 0)
        {
          cout << "i=" << i << " j=" << j << " k=" << k << " len=" << arr[i][j][k] << endl;
          string str(str1+k-sub_str_len, str1+k);
          cout << "ccccc = " << str << endl;
        }
      }
    }
  }
  return;
}



int main(int argc, char **argv)
{
  const char *str1 = argv[1];
  const char *str2 = argv[2];
  const char *str3 = argv[3];

  max_sub_str(str1, str2, str3);

  max_sub_str_new(str1, str2, str3);
  return 0;
}