codeiq ストリング問題 提出版は32bitの限界を考慮漏れして不正解

gemstring.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>

static int mpermulate(char *prefix, char *array, char *match, long long* count)
{
  char gemstring[16];
  char newarray[16];
  char last;

  if (*array == '\0')
    return 0;

  int i;
  int arrlen =  strlen(array);
  int prelen =  strlen(prefix);

  last = '\0';
  for (i = 0; i < arrlen; i++) {
    // aaabcc 同じ文字が続いていた場合は省略
    if (last == array[i]) continue;

    // prefix + 先頭文字で新しい組み合わせを作る
    // eg: aaa + b
    memmove(gemstring, prefix, prelen);
    memmove(gemstring + prelen, array + i, 1);
    gemstring[prelen + 1] = '\0';

    (*count)++;
    if (!strcmp(gemstring, match)) {
#ifdef PRINT
      printf("%s\n",gemstring);
      printf("count = %lld\n",*count);
#endif
      return *count;
    }

    // 現在対象にしている文字以外の新しいarrayを作成する
    // eg: b:[aaabcc] -> [aaacc])
    memmove(newarray, array, i);
    memmove(newarray + i,array + (i + 1), arrlen - (i + 1));
    newarray[i + arrlen - (i + 1)] = '\0';

    if (mpermulate(gemstring, newarray, match, count) > 0) {
      return *count;
    }
    last = array[i];
  }
  return 0;
}

int main(void)
{
  long long count;

#if 0
  count = 0;assert((mpermulate("",  "aaabcc",  "ccbaaa",  &count)) == 188);
  count = 0;assert((mpermulate("",  "aaabcc",  "a",  &count)) == 1);
  count = 0;assert((mpermulate("",  "aaabcc",  "acb",  &count)) == 73);
  count = 0;assert((mpermulate("",  "aaabcc",  "cc",  &count)) == 175);
#else
  mpermulate("", "abbbbcddddeefggg", "eagcdfbe", &count);
  printf("count = %lld\n", count);
#endif

  return 0;
}

gemstring.cc

/*
 * メモ化バージョン
 */
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <iostream>
#include <map>
#include <string>

typedef std::string string_t;
typedef std::map<string_t, long long> memo_t;
typedef std::pair<string_t, long long> elem_t;

class Stack {

private:
  char buffer_[16];
  int index_;
public:
  Stack():index_(0) {
    memset(buffer_, 0, sizeof(buffer_));
  }
  void push(char c) {
    buffer_[index_++] = c;
  }
  char pop() {
    if (index_ <= 0)
      return -1;
    return  buffer_[--index_];
  }
  string_t to_str() {
    char tmp[16];
    memcpy(tmp,buffer_, index_ );
    tmp[index_] = '\0';

    return string_t(tmp);
  }
};

static long long remember_number(char *gems,memo_t& memo)
{
  memo_t::iterator p;
  string_t gem_s(gems);

  if ( (p = memo.find(gem_s)) == memo.end() ) {
    return 0;
  } else {
    return p->second;
  }
}
static void memorize_number(memo_t& memo ,char *gems, int numofpattern)
{
  string_t gem_s(gems);
  memo.insert( elem_t(gem_s, numofpattern) );
}

static long long mpermulate2(char* pattern, char *gems, memo_t& memo, Stack& prefix, long long *result)
{
  if (!*gems)
    return 0;
  /*
   * メモ化を行って宝石パターンの数の探索をスキップする場合には、
   * スキップする範囲に王女様のパターンが含まれていないか
   */
  string_t prefix_t    = prefix.to_str();
  string_t pattern_s = string_t(pattern);

  if (pattern_s.find(prefix_t) != 0) {
    long long memorized = remember_number(gems, memo);
    if (memorized) {
      (*result) += memorized;
      return memorized;
    }
  }

  char      newgems[16];
  long long sum    = 0;
  int       gemlen = strlen(gems);
  char      last   = '\0';

  for (int i = 0; i < gemlen; i++) {
    // 同じ文字が繰り返すパターンはループさせない
    // "eg:aaa"
    if (gems[i] == last) continue;

    prefix.push(gems[i]);
    sum++; (*result)++;

    //プレフィックスに1つ追加したものがこれから探すパターン
    string_t target_s = prefix.to_str();

    if (pattern_s == target_s)
      std::cout << "found!!: "<< target_s << " count = " << *result << std::endl;

    memmove(newgems, gems, i);
    memmove(newgems + i,gems + (i + 1), gemlen - (i + 1));
    newgems[i + gemlen - (i + 1)] = '\0';
    sum += mpermulate2(pattern, newgems, memo, prefix, result);
    last = gems[i];
    prefix.pop();
  }
  memorize_number(memo, gems, sum);
  return sum;
}

int main(void)
{
  long long result = 0;
  Stack stack;
  memo_t memo;

  char gems[]    = "abbbbcddddeefggg";
  char pattern[] = "eagcdfbe";
  std::cout << mpermulate2(pattern, gems, memo, stack, &result) << std::endl;

  return 0;
}