#include<iostream>
#include<stdio.h>
#include<string.h>
#include<vector>
#include<fstream>
#include<cstddef>
using namespace std;

int main()
{
      ifstream fin;
      fin.open("CYK.txt");
      vector<string> pr;
      string s,str="";
      
      while(!fin.eof())
      {
       getline(fin,s);
       cout<<s<<endl;
       pr.push_back(s);                 
      }
      
	  int nor = pr.size();
      for(int i=0; i<nor;i++)
      {
              if(pr[i][0]=='S')
              {
                               str = pr[i];
                               break;
              }
      }
     
       if(str =="") 
       { 
              cout<<" Invalid Grammar";
              return 0;
       }
      
       char rs[nor];
       for(int i=0; i<nor;i++)
       rs[i]= pr[i][0];
   
       string temp;
       vector<string> ls[nor];
       
       size_t f;
      for(int i=0; i<nor;i++)
      {
        f = pr[i].find_first_of('|');
        temp = pr[i].substr(3,f-3);
        while(f!=std::string::npos)
        {
        	int t=f+1;
			f=pr[i].find('|',f+1);
        	temp = pr[i].substr(t,f-t);
        	ls[i].push_back(temp);
        }
     }
		
	 
      string ip;
      cout<<"Enter String = ";
      cin>>ip;
      string tempo="";
      int len = ip.length();
      vector <string> TT[len];
      for(int i=0; i<len; i++)
      {    
	      temp ="";    
              temp = temp + ip[i];
              for(int k=0; k<nor;k++)
              {
                
                for(int j=0; j<ls[k].size();j++)
                {      
				  if(ls[k][j].compare(temp)==0)
                  TT[0][i]=TT[0][i]+rs[k];
                }
              }
       }
           
 cout<<TT[0];
   return 0;  
}