E.密码(算法选修)

松塔先生决定在他的电脑上下载原神来玩，但是他的队友灵妹妹觉着玩游戏实在是太浪费时间了，于是灵妹妹给松塔先生的原神下载界面上了锁，并丢给松塔先生一串字符。 现在有三种子串： 1.子串是该字符串的前缀 2.子串是该字符串的后缀 3.子串既不是该字符串的前缀也不是该字符串的后缀 密码就是满足这三种条件的最长子串。 即密码既是字符串的前缀，又是字符串的后缀，且在字符串中以非前后缀的形式出现过。 但是松塔先生太懒了，宁可睡觉也不解密码，请你帮助他。 特别的，由于灵妹妹特别的狡猾，密码可能根本就不在这串字符串里，如果是这样，输出"Play what play,Roll to study"

Input

多行由小写英文字母组成的字符串，长度n(1<=n<=1e6)

Output

多行字符串，原神下载页面的密码或者"Play what play,Roll to study" 末尾有换行

Sample Input

abcdefabcghaabc abc

Sample Output

abc Play what play,Roll to study

  

   

    

     

    
    

     

      #include<iostream>
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      using 
      namespace std;
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     

          ios::
      sync_with_stdio(
      false), cin.
      tie(
      nullptr), cout.
      tie(
      nullptr);
     
    
   

    

     

    
    

     

          string a,b,c,d;
     
    
   

    

     

    
    

     
    
      while(cin>>a)
     
    
   

    

     

    
    

     

          {
     
    
   

    

     

    
    

     

              b=a;
     
    
   

    

     

    
    

     
        
      int k=
      0,num=
      0,kb=
      -1;
     
    
   

    

     

    
    

     
        
      reverse(b.
      begin(),b.
      end());
     
    
   

    

     

    
    

     

              string A,B;
     
    
   

    

     

    
    

     

              A.
      empty();
     
    
   

    

     

    
    

     

              B.
      empty();
     
    
   

    

     

    
    

     
        
      for(
      int i=
      0;i<(
      int)a.
      length()
      -1;i++)
     
    
   

    

     

    
    

     

              {
     
    
   

    

     

    
    

     

                  A+=a[i];
     
    
   

    

     

    
    

     

                  B+=b[i];
     
    
   

    

     

    
    

     
            
      for(
      int j=
      0;j<(
      int)A.
      length();j++)
     
    
   

    

     

    
    

     

                  {
     
    
   

    

     

    
    

     
                
      if(a[j]==b[A.
      length()-j
      -1])
     
    
   

    

     

    
    

     

                          k=
      0;
     
    
   

    

     

    
    

     
                
      else
     
    
   

    

     

    
    

     

                      {
     
    
   

    

     

    
    

     

                          k=
      1;
     
    
   

    

     

    
    

     
                    
      break;
     
    
   

    

     

    
    

     

                      }
     
    
   

    

     

    
    

     

                  }
     
    
   

    

     

    
    

     
            
      if(k==
      0)
     
    
   

    

     

    
    

     

                  {
     
    
   

    

     

    
    

     

                      c=A;
     
    
   

    

     

    
    

     
                
      int pos=a.
      find(c,
      1);
     
    
   

    

     

    
    

     
                
      if((pos+c.
      length()
      -1)<(a.
      length()
      -1))
     
    
   

    

     

    
    

     

                      {
     
    
   

    

     

    
    

     
                    
      int len=c.
      length();
     
    
   

    

     

    
    

     
                    
      if(len>kb)
     
    
   

    

     

    
    

     

                          {
     
    
   

    

     

    
    

     

                              kb=len;
     
    
   

    

     

    
    

     

                              d=c;
     
    
   

    

     

    
    

     

                              num=
      1;
     
    
   

    

     

    
    

     

                          }
     
    
   

    

     

    
    

     

                      }
     
    
   

    

     

    
    

     
                
      else
     
    
   

    

     

    
    

     
                    
      continue;
     
    
   

    

     

    
    

     

                  }
     
    
   

    

     

    
    

     

              }
     
    
   

    

     

    
    

     
        
      if(num==
      0)
     
    
   

    

     

    
    

     

                  cout<<
      "Play what play,Roll to study"<<endl;
     
    
   

    

     

    
    

     
        
      else
     
    
   

    

     

    
    

     

                  cout<<d<<endl;
     
    
   

    

     

    
    

     

          }
     
    
   

    

     

    
    

     
    
      return 
      0;
     
    
   

    

     

    
    

     

      }