Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- const int mx = 1010;
- ll dp[mx][4],L,R=3;
- string s,s1="KEK";
- ll solve(int a,int b)
- {
- if(L<a || R<b)
- return 0;
- if(R==b)
- return 1;
- if(L==a)
- return 0;
- if(dp[a][b]!=-1)
- return dp[a][b];
- if(s[a]==s1[b])
- dp[a][b]=solve(a+1,b+1)+solve(a+1,b);
- else
- dp[a][b]=solve(a+1,b);
- return dp[a][b];
- }
- int main()
- {
- int t;
- cin>>t;
- while(t--)
- {
- cin>>s;
- memset(dp,-1,sizeof(dp));
- L=s.size();
- cout<<solve(0,0)<<endl;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement