DigitMultiples

日課消化。部分文字列比較アルゴリズムの良い勉強になりました。

class DigitMultiples {
private:
	struct node {
	  int value;
	  node *next;
	  node(int value, node *next) : value(value), next(next) { }
	};

	#define index_of(as, x) \
	  distance(as.begin(), lower_bound(as.begin(), as.end(), x))

	string lcs_hs(const string &a, const string &b) {
	  const int n = a.size(), m = b.size();
	  map< char, vector<int> > M;
	  for (int j = m-1; j >= 0; --j)
	    M[ b[j] ].push_back( j );
	  vector<int> xs(n+1, 99999999); xs[0] = -99999999;
	  vector< node* > link(n+1);
	  for (int i = 0; i < n; ++i) {
	    if (M.count(a[i])) {
	      vector<int> ys = M[a[i]];
	      for (unsigned int j = 0; j < ys.size(); ++j) {
	        int k = index_of(xs, ys[j]);
	        xs[k] = ys[j];
	        link[k] = new node(b[ ys[j] ], link[k-1]);
	      }
	    }
	  }
	  int l = index_of(xs, 99999999-1) - 1;

	  string c;
	  for (node *p = link[l]; p; p = p->next)
	    c.push_back(p->value);
	  reverse(c.begin(), c.end());
	  return c;
	}

	string IntToString(int number)
	{
	  stringstream ss;
	  ss << number;
	  return ss.str();
	}

public:
	int getLongest(string single, string multiple) {
		unsigned int result = 0;
		for(int k=0;k<=9;k++){
			string str = single;
			for(unsigned int i=0; i<str.size(); i++){
				str[i] = '0' + (str[i] - '0') * k;
			}
			result = max(result, lcs_hs(str,multiple).size());
		}
		return result;
	}
};