Advertisement
Farjana_akter

Untitled

Jun 5th, 2020
48
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.91 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long int ll;
  4.  
  5. int lcs(string a,string b)
  6. {
  7. int l1=a.size();
  8. int l2=b.size();
  9. int lcs[l1+5][l2+5];
  10. for(int i=0; i<=l1; i++)
  11. {
  12. for(int j=0; j<=l2; j++)
  13. {
  14. if(i==0 || j==0)
  15. lcs[i][j]=0;
  16. else if(a[i-1]!=b[j-1])
  17. {
  18. if(lcs[i-1][j]>lcs[i][j-1])
  19. lcs[i][j]=lcs[i-1][j];
  20. else
  21. lcs[i][j]=lcs[i][j-1];
  22. }
  23. else if(a[i-1]==b[j-1])
  24. {
  25. lcs[i][j]=lcs[i-1][j-1]+1;
  26. }
  27. }
  28. }
  29.  
  30. return lcs[l1][l2];
  31. }
  32.  
  33.  
  34. ll pos[100005];
  35. int main()
  36. {
  37. string s,p;
  38. ll t,i,j,k;
  39. cin>>t;
  40. while(t--)
  41. {
  42. cin>>s>>p;
  43. ll len=s.size();
  44. char c;
  45. c=p[0];
  46. ll x=0;
  47. for(i=0; i<s.size(); i++)
  48. {
  49. if(s[i]==c)
  50. {
  51. pos[x++]=i;
  52. }
  53. }
  54. string str[x+5],a,b,d;
  55. if(pos[0]==0)
  56. {
  57. str[0]=s;
  58. for(i=1; i<x; i++)
  59. {
  60. a=s.substr(0,pos[i]);
  61. b=s.substr(pos[i],len-1);
  62. str[i]=b+a;
  63. }
  64. }
  65. else
  66. {
  67. for(i=0; i<x; i++)
  68. {
  69. a=s.substr(0,pos[i]);
  70. b=s.substr(pos[i],len-1);
  71. d=b+a;
  72. str[i]=b+a;
  73. }
  74. }
  75. int flag=0;
  76. for(i=0; i<x; i++)
  77. {
  78. int m=lcs(str[i],p);
  79. if(m==p.size())
  80. {
  81. flag=1;
  82. break;
  83. }
  84. }
  85. if(flag==1)
  86. {
  87. cout<<"Ekka is not a Liar!"<<endl;
  88. }
  89. else
  90. {
  91. cout<<"Ekka is a Liar!"<<endl;
  92. }
  93. }
  94. return 0;
  95. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement