Repeat pattern

Given a vector containing an arbitrary numbers of integers, check if there any repeat pattern in it.

I found this problem in CodeEval, where is marked with the slightly misleading name of Detecting Cycles (usually we talk about detecting cycles in the domain of graphs, here we have to do with a plain vector). There you could also find a test case that helps to clarify what our function has to do. I have rewritten it in C++11 for the GoogleTest framework:

std::vector<int> solution(const std::vector<int>& input);

TEST(DeCy, Given)
{
  std::vector<int> result = solution( {2, 0, 6, 3, 1, 6, 3, 1, 6, 3, 1} );

  ASSERT_EQ(3, result.size());
  ASSERT_EQ(6, result[0]);
  ASSERT_EQ(3, result[1]);
  ASSERT_EQ(1, result[2]);
}

As you see, here there is a repeat pattern of three integers (3, 1, 6). Our function should detect it and return it.

Our input could be much more complicated, so I have written a few more test cases, but I spare you. However you should notice that the minimal case is when the pattern consist of just a number that appear twice.

I have interpreted the problem request in the most natural way, so that I can split it in two logical parts. Firstly I check if there is at least a repeated integer in the sequence. If I find it, I check how long is the pattern, filling a vector with each matching element.

This algorithm scales terribly, in the worst case it has a cubic (!) asymptotically time complexity. Any improvement suggestion is welcomed. In the meantime, here is my C++98 implementation:

std::vector<int> solution(const std::vector<int>& input)
{
  if(input.size() < 2)
    return std::vector<int>(); // 1

  for(std::vector<int>::const_iterator first = input.begin(); first != input.end() - 1; ++first) // 2
  {
    for(std::vector<int>::const_iterator second = first + 1; second != input.end(); ++second) // 3
    {
      if(*first != *second)
        continue;

      int len = second - first; // 4
      if(second + len > input.end())
        len = input.end() - second;

      for(int i = 0; i < len; ++i)
      {
        if(*(first+i) != *(second+i)) // 5
          len = i;
      }

      return std::vector<int>(first, first + len);
    }
  }

  return std::vector<int>();
}

1. The input sequence has one or no element, there is not much to do besides returning an empty vector.
2. Loop on all the elements (but the last one).
3. Loop on the elements following the first iterator.
4. The first and second characters match, calculate their distance. The pattern couldn't be bigger than that. Wait a minute, we should also consider the vector size, that could put a lower limit the the pattern length.
5. Find the actual pattern size, if less than the theoretical maximum length.