len_LRS.cpp

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

using namespace std;

int longest_repeated_string(string text){
  map<string, vector<int>> substrings;
  int search_length = 2;

  while(true){
    index_all_substrings(text, search_length, substrings);
    list<map<string, vector<int>>::iterator> unique_substrings = find_unique_substrings(substrings);
    erase_list_from_map(substrings, unique_substrings);

    if(substrings.empty()) {
      return search_length - 1;
    }else{
      search_length++;
    }
  }
}

void index_all_substrings(string text, int length, map<string, vector<int>> &indexes){
  indexes.clear();
  for(int i = 0; i < text.length()-(search_length-1); i++){
    indexes[text.substr(i, search_length)].push_back(i);
  }
}

list<map<string, vector<int>>::iterator find_unique_substrings(map<string, vector<int>> indexes) {
  map<string, vector<int>>::iterator itr;
  list<map<string, vector<int>>::iterator> unique_substrings;

  for(itr = indexes.begin(); itr != indexes.end(); itr++){
    if(itr->second.size() <= 1){
      unique_substrings.push_back(itr);
    }
  }

  return unique_substrings;
}

void erase_list_from_map(map<string, vector<int>> &map, list<map<string, vector<int>>> list){
  list<map<string, vector<int>>::iterator>::iterator list_itr;
  for(list_itr = list.begin(); list_itr != list.end(); list_itr++){
    map.erase(*list_itr);
  }
}

int main(){

	ifstream file;
	string text;
	string line;

	file.open("short_moby_dick.txt");
	while(getline(file, line)) text += line;
	file.close();

	//string text = "123456789123456789123";

	cout << longest_repeated_string(text) << endl;

	return 0;
}