fork download
copy 
  1. #include <iostream>
  2. #include <cstring>
  3. using namespace std;
  4. char s[5001];
  5. char w[5001];
  6. struct node
  7. {
  8.     node *pointer[2];
  9.     int count;
  10. 	bool used;
  11. 	node()
  12. 	{
  13. 		pointer[0] = pointer[1] = NULL;
  14. 		used = false;
  15. 		count = 0;
  16. 	}
  17. };
  18. node root;
  19. int dfs(node *cur)
  20. {
  21. 	if (cur==NULL || !cur->used)
  22. 	{
  23. 		return 0;
  24. 	}
  25. 	else
  26. 	{
  27. 		cur->count = 1 + dfs(cur->pointer[1]) + dfs(cur->pointer[0]); 
  28. 		return cur->count;
  29. 	}
  30. }
  31. int ansSize = 0;
  32. char ans[5001];
  33. void go(node* cur, int k)
  34. {
  35. 	if (cur==NULL || k==0 || k>cur->count)
  36. 	{
  37. 		cout<<"ERROR"<<endl;
  38. 		return;
  39. 	}
  40. 	if (k==1) 
  41. 	{
  42. 		return;
  43. 	}
  44. 	k--;
  45. 	if (cur->pointer[0]!=NULL && k<=cur->pointer[0]->count)
  46. 	{
  47. 		ans[ansSize++] = '0';
  48. 		go(cur->pointer[0], k);
  49. 	}
  50. 	else
  51. 	{
  52. 		ans[ansSize++] = '1';
  53. 		if (cur->pointer[0] != NULL)
  54. 		{
  55. 			k -= cur->pointer[0]->count;
  56. 		}
  57. 		go(cur->pointer[1], k);
  58. 	}
  59. }
  60. int main()
  61. {   
  62. 	int k;
  63. 	cin>>s>>w>>k;
  64. 	k++;
  65. 	int n = strlen(s);
  66. 	for (int i=0;i<n;i++)
  67. 	{
  68. 		node *cur = &root;
  69. 		for (int j=i;j<n;j++)
  70. 		{
  71. 			char t = s[j]-'0';
  72. 			if (cur->pointer[t]==NULL)
  73. 			{
  74. 				cur->pointer[t] = new node();
  75. 			}
  76. 			cur=cur->pointer[t];
  77. 		}
  78. 	}
  79. 	n = strlen(w);
  80. 	root.used = true;
  81. 	for (int i=0;i<n;i++)
  82. 	{
  83. 		node *cur = &root;
  84. 		for (int j=i;j<n;j++)
  85. 		{
  86. 			char t = w[j]-'0';
  87. 			if (cur->pointer[t] == NULL)
  88. 			{
  89. 				break;
  90. 			}
  91. 			else
  92. 			{
  93. 				cur = cur->pointer[t];
  94. 				cur->used = true;
  95. 			}
  96. 		}
  97. 	}
  98. 	dfs(&root);
  99. 	go(&root, k);
  100. 	cout<<ans<<endl;
  101. 	return 0;
  102. }
  103.  
Success #stdin #stdout 0s 3000KB
comments (?)
stdin
copy 
0100
0010
3
stdout
copy 
01
https://ideone.com/TGMaxI
language:
C++ (gcc 8.3)
created:
11 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!