#include <algorithm>
#include <string>
#include <vector>
#include <iostream>

using namespace std;

string theString;		//HACK
int n;
vector<vector<int> > _memo;

int f(int i, int j);		// Need forward declaration for mutual recursion

int m(int i, int j) {
	return static_cast<int>(theString[i - 1] == theString[j - 1] && i < j) + f(i - 1, j - 1);
}

int f(int i, int j) {
	if (i == 0 || j == 0) {
		return 0;
	}
	
	// Make sure the DP table is big enough
	if (_memo.size() <= i) {
		_memo.resize(i + 1);
	}
	if (_memo[i].size() <= j) {
		_memo[i].resize(j + 1, -1);		// -1 means "dunno yet"
	}
	
	if (_memo[i][j] == -1) {
		// Dunno the answer yet, need to compute it
		_memo[i][j] = max(max(f(i - 1, j), f(i, j - 1)), m(i, j));
	}
	
	return _memo[i][j];
}

int longestSACS(string s) {
	// Clear the DP table
	_memo.clear();
	theString = s;
	n = theString.size();
	
	int x = 0;
	for (int i = 0; i <= n; ++i) {
		x = max(x, f(i, n));
	}
	
	return x;
}

int main(int argc, char **argv) {
	cout << longestSACS("1213213515") << '\n';
	cout << longestSACS("1213243545") << '\n';
	return 0;
}