fork download 
  1. #include <iostream>
  2. #include <cstdio>
  3.  
  4. using namespace std;
  5.  
  6. int recurse(string s, int **arr, int n, int i, int j)
  7.  
  8. {
  9.     if(i < 0 || j >= n)return 0;
  10.  
  11.     if(arr[i][j] != -1)return arr[i][j];
  12.  
  13.     if(s[i] == s[j]){ arr[i][j] = 1 + recurse(s,arr,n,i-1,j+1); return arr[i][j];}
  14.  
  15.     // otherwise s[i] != s[j]
  16.     arr[i][j] = 0;
  17.     return arr[i][j];
  18. }
  19.  
  20. int findLongestRepeated(string s, int **arr, int n)
  21.  
  22. {
  23.     int answer = 0;
  24.  
  25.     for(int i = 0 ; i < n ; ++i)
  26.     {
  27.         for(int j = i + 1 ; j < n ; ++j)
  28.         {
  29.             if(arr[i][j] == -1)
  30.                 arr[i][j] = recurse(s,arr,n,i,j); //this assignment happens anyway in the function recurse.
  31.  
  32.             answer = max(answer,arr[i][j]);
  33.         }
  34.     }
  35.  
  36.     return answer;
  37. }
  38.  
  39. int main()
  40. {
  41.     string inp;
  42.     cin>> inp;
  43.  
  44.     int len = inp.length();
  45.  
  46.     int **table = new int*[len+1];
  47.  
  48.     for(int i = 0 ; i <= len ; ++i)
  49.     {
  50.         table[i] = new int[len+1];
  51.         for(int j = 0 ; j <= len ; ++j)
  52.             table[i][j] = -1;
  53.     }
  54.  
  55.     cout<<findLongestRepeated(inp,table,len)<<endl;
  56.  
  57.     return 0;
  58. }
  59.  
Success #stdin #stdout 0s 3480KB
comments (?)
stdin 
kumarxyzramuk
stdout 
5
https://ideone.com/Qzs990
language:
C++ (gcc 8.3)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!