fork(42) download
  1. #include<bits//stdc++.h>
  2. using namespace std;
  3. #define INF 1e8
  4. bool check(char a, char b)
  5. {
  6. if(a==b)
  7. return 1;
  8. if(a=='a'&&b=='o')
  9. return 1;
  10. if(a=='o'&&b=='a')
  11. return 1;
  12. if(a=='t'&&b=='l')
  13. return 1;
  14. if(a=='l'&&b=='t')
  15. return 1;
  16. return 0;
  17. }
  18.  
  19. int main()
  20. {
  21. int n;
  22. cin>>n;
  23. string draw_string;
  24. cin>>draw_string;
  25. string ticket[n];
  26. for(int i=0;i<n;i++)
  27. {
  28. cin>>ticket[i];
  29. }
  30. int k;
  31. cin>>k;
  32. int ans=0;
  33. for(int i=0;i<n;i++)
  34. {
  35. int dp[201][201][2][2];
  36. int sz2=draw_string.size(),sz1=ticket[i].size();
  37. for(int j=0;j<sz1;j++)
  38. {
  39. dp[j][sz2][0][0]=INF;
  40. dp[j][sz2][1][0]=INF;
  41. dp[j][sz2][0][1]=INF;
  42. dp[j][sz2][1][1]=INF;
  43. }
  44. dp[sz1-1][sz2][0][1]=0;
  45. dp[sz1-1][sz2][1][1]=0;
  46. for(int j=0;j<=sz2;j++)
  47. {
  48. dp[sz1][j][0][0]=0;
  49. dp[sz1][j][1][0]=0;
  50. dp[sz1][j][0][1]=0;
  51. dp[sz1][j][1][1]=0;
  52. }
  53. for(int j=sz1-1;j>=0;j--)
  54. {
  55. for(int k=sz2-1;k>=0;k--)
  56. {
  57. if(check(ticket[i][j],draw_string[k]))
  58. {
  59. dp[j][k][0][0]=min(dp[j+1][k+1][1][0],dp[j][k+1][0][0]);
  60. dp[j][k][1][0]=dp[j+1][k+1][1][0];
  61. }
  62. else
  63. {
  64. dp[j][k][0][0]=dp[j][k+1][0][0];
  65. dp[j][k][1][0]=1+dp[j][k+1][1][0];
  66. }
  67. if(check(ticket[i][j],draw_string[k]))
  68. {
  69. dp[j][k][0][1]=min(dp[j+1][k+1][1][1],dp[j][k+1][0][1]);
  70. dp[j][k][1][1]=dp[j+1][k+1][1][1];
  71. }
  72. else
  73. {
  74. dp[j][k][0][1]=min(dp[j][k+1][0][1],dp[j+1][k+1][0][0]);
  75. dp[j][k][1][1]=min(1+dp[j][k+1][1][1],dp[j+1][k+1][1][0]);
  76. }
  77. }
  78. }
  79. if(dp[0][0][0][1]<=k)
  80. ans++;
  81. }
  82. cout<<ans<<endl;
  83. return 0;
  84. }
Success #stdin #stdout 0s 5396KB
stdin
3 
aabacd 
abcde 
aoc 
actld 
1
stdout
2