fork download
copy 
  1. #include<bits/stdc++.h>
  2.  
  3. // #include <ext/pb_ds/assoc_container.hpp>
  4. // #include <ext/pb_ds/tree_policy.hpp>
  5. #include<unordered_map>
  6. #include<unordered_set>
  7. #include<stdio.h>
  8. #include<stdlib.h>
  9. typedef long long ll;
  10. typedef unsigned long long ull;
  11. #define pi 3.1415926535
  12. #define mod 1000000007    
  13. // #define mod 99999997                 //change when needed
  14.  
  15. using namespace std;
  16. // using namespace __gnu_pbds;
  17. template <typename T>
  18. T InvMod(T a,T b,T &x,T &y)
  19. {
  20.     if(a==0)
  21.     {
  22.         x=0;
  23.         y=1;
  24.         return b;
  25.     }
  26.     T x1,y1;
  27.     T g=InvMod(b%a,a,x1,y1);
  28.     x=y1-(b/a)*x1;
  29.     y=x1;
  30.     return g;
  31. }
  32. template <typename T>
  33. T gcd(T a,T b)
  34. {
  35.     if(b==0) return a;
  36.     return gcd(b,a%b);
  37. }
  38. template <typename T>
  39. ll mod_exp(T a,T b,ll m)
  40. {
  41.     if(b==0) return 1;
  42.     if(b==1) return a%m;
  43.     T tmp=mod_exp(a,b/2,m);
  44.     if(b%2==1)
  45.     {
  46.         return ((tmp%m*tmp%m)%m*a%m)%m;
  47.     }
  48.     else
  49.     {
  50.         return (tmp%m*tmp%m)%m;
  51.     }
  52. }
  53.  
  54. //------------------------------------------------------------------------------------------------------------------------------------------------//
  55. struct HASH{
  56.   size_t operator()(const pair<ll,ll>&x)const{
  57.     return hash<long long>()(((long long)x.first)^(((long long)x.second)<<40));
  58.   }
  59. };
  60. int main()
  61. {
  62.     ios_base::sync_with_stdio(0);
  63.     cin.tie(0);
  64.     cout.tie(0);
  65.     int t=1;
  66.     // cin>>t;
  67.     while(t--)
  68.     {
  69.         string s;
  70.         getline(cin,s);
  71.         string p;
  72.         getline(cin,p);
  73.         int n;
  74.         cin>>n;
  75.         string tmp=p;
  76.         tmp=tmp+'`'+s;
  77.         // cout<<tmp<<"\n";
  78.         vector<int> z(tmp.length(),0);
  79.         int L=0,R=0;
  80.         for (int i=1;i<tmp.length();i++) 
  81.         {
  82.             if(i>R) 
  83.             {
  84.                 L=R=i;
  85.                 while(R<tmp.length()&&tmp[R-L]==tmp[R]) 
  86.                 {
  87.                     R++;
  88.                 }
  89.                 z[i]=R-L; 
  90.                 R--;
  91.             } 
  92.             else 
  93.             {
  94.                 int k=i-L;
  95.                 if (z[k]<R-i+1) 
  96.                 {
  97.                     z[i]=z[k];
  98.                 } 
  99.                 else 
  100.                 {
  101.                     L=i;
  102.                     while (R<tmp.length()&&tmp[R-L]==tmp[R]) 
  103.                     {
  104.                         R++;
  105.                     }
  106.                     z[i]=R-L; 
  107.                     R--;
  108.                 }
  109.             }
  110.             // cout<<z[i]<<" ";
  111.         }
  112.         int arr[s.length()+1];
  113.         memset(arr,0,sizeof arr);
  114.         for(int i=p.length()+1;i<tmp.length();i++)
  115.         arr[z[i]]++;
  116.         // cout<<endl;
  117.         int ans=0;
  118.         int cnt=0;
  119.         for(int i=s.length();i>=0;i--)
  120.         {
  121.             // cout<<i<<" "<<arr[i]<<"\n";
  122.             cnt+=arr[i];
  123.             if(cnt>=n)
  124.             {
  125.                 ans=i;
  126.                 break;
  127.             }
  128.         }
  129.         if(ans==0)
  130.         {
  131.             cout<<"IMPOSSIBLE\n";
  132.         }
  133.         else
  134.         cout<<s.substr(0,ans)<<"\n";
  135.     }
  136. }
Success #stdin #stdout 0s 4164KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
IMPOSSIBLE
https://ideone.com/UO3Tgb
language:
C++14 (gcc 8.3)
created:
4 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!