Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- typedef long long int ll;
- int lcs(string a,string b)
- {
- int l1=a.size();
- int l2=b.size();
- int lcs[l1+5][l2+5];
- for(int i=0; i<=l1; i++)
- {
- for(int j=0; j<=l2; j++)
- {
- if(i==0 || j==0)
- lcs[i][j]=0;
- else if(a[i-1]!=b[j-1])
- {
- if(lcs[i-1][j]>lcs[i][j-1])
- lcs[i][j]=lcs[i-1][j];
- else
- lcs[i][j]=lcs[i][j-1];
- }
- else if(a[i-1]==b[j-1])
- {
- lcs[i][j]=lcs[i-1][j-1]+1;
- }
- }
- }
- return lcs[l1][l2];
- }
- ll pos[100005];
- int main()
- {
- string s,p;
- ll t,i,j,k;
- cin>>t;
- while(t--)
- {
- cin>>s>>p;
- ll len=s.size();
- char c;
- c=p[0];
- ll x=0;
- for(i=0; i<s.size(); i++)
- {
- if(s[i]==c)
- {
- pos[x++]=i;
- }
- }
- string str[x+5],a,b,d;
- if(pos[0]==0)
- {
- str[0]=s;
- for(i=1; i<x; i++)
- {
- a=s.substr(0,pos[i]);
- b=s.substr(pos[i],len-1);
- str[i]=b+a;
- }
- }
- else
- {
- for(i=0; i<x; i++)
- {
- a=s.substr(0,pos[i]);
- b=s.substr(pos[i],len-1);
- d=b+a;
- str[i]=b+a;
- }
- }
- int flag=0;
- for(i=0; i<x; i++)
- {
- int m=lcs(str[i],p);
- if(m==p.size())
- {
- flag=1;
- break;
- }
- }
- if(flag==1)
- {
- cout<<"Ekka is not a Liar!"<<endl;
- }
- else
- {
- cout<<"Ekka is a Liar!"<<endl;
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement