SPOJ (ONLINE JUDGE) CODING CONTEST PROBLEM

                                       SPOJ PROBLEM

You are working on a new “RPG Hero Name Generator” application. In order to generate the names, rather than going for a dictionary approach you decide to explore something more along the lines of Markov-chain text generation. Since you are generating character names rather than paragraphs, you treat each character as a state, and in order to simplify matters you make the assumption that each letter is independent of all of the letters coming before it except for its immediate predecessor.

The input consists of two lines. The first character of the first line is the character to be considered. The rest of the line will consist of an arbitrary number of characters, this is the sample of text to be considered. Ignore the content of the second line. You are to output a single character, the one which occurs most frequently after the given character in the sample.

The number of characters is small enough that you need not worry about exceeding the limits of int. The character string will consist of only uppercase or lowercase alphabets, you will not encounter any other characters.

Example

Input

aabcdefghijklmnopqrstuvwxyza

Output

b

SO I HAVE WRITTEN A SIMPLE CODE FOR THIS.....AGAIN ENJOY PROGRAMMING....:)

#include<iostream>
#include<vector>
#include<stdio.h>
#include<stdlib.h>
#include<queue>
#include<list>
#define show(x) copy(x.begin(),x.end(),output)
#include<iterator>
#define sort(x) sort(x.begin(),x.end())
#include<string>
#define vs vector<string>
#define vi vector<int>
#define pb push_back
#include<map>
#include<algorithm>
#include<sstream>
#include<stack>
#include<cmath>
#include<cstring>
#include<iomanip>
#include<cctype>
using namespace std;
class saurabh
{
      public:
      char find( string s)
      {
           int count = 0;
           int temp = 0;
           int index = 0;
           int position = 0;
           char f = s[0];
           stringstream ss;
           ss<<f;
           char ret;
           position = s.find(ss.str());
           index = count + position;
           while(position != string ::npos)
           {
                          count = 0;
                          for(int i = position ; i < s.size() ; i++)
                          {
                                  if(s[i] == f)
                                  {
                                          count++;
                                  }
                                  else
                                  {
                                      break;
                                  }
                          }
                          if( temp < count)
                          {
                              temp = count;
                              index = count + position ;
                          }     
                          position = s.find(f,position+1);
           }
           ret = s[index];
           return ret;
      }
};
  int main()
  {
      string s = "aabcdefghijklmnoaaaapqrstuvwxyza";
      saurabh p;
      char c = p.find(s);               
      cout<<c<<endl;
      cin.get();
      return 0;
  }                       

                                         

BY: SAURABH BHATIA (GNDU , RC , JAL)