fork download
copy 
  1. #include <iostream>
  2. #include <algorithm>
  3.  
  4. int main(){
  5. 	std::string word1;
  6. 	std::string word2;
  7. 	int i;
  8. 	int j;
  9. 	bool flag = true;
  10. 	bool flag1 = false;
  11. 	bool flag2 = false;
  12. 	bool flag3 = false;
  13. 	bool flag4 = false;
  14. 	bool flag5 = false;
  15. 	std::string rez = "";
  16. 	//ввод первого слова
  17. 	while (true){
  18. 		std::cout << "Введите первое слово, состоящее из букв 'а', 'г', 'ц', 'т' : ";
  19. 		std::cin >> word1;
  20. 		std::cout << word1 << std::endl;
  21. 		for (i = 0; i < word1.length(); i++)
  22. 			if (word1[i] == 'a' || word1[i] == 'r' || word1[i] == 'c' || word1[i] == 't'|| word1[i] == '\0')
  23. 				flag1 = true;
  24. 			else
  25. 				flag1 = false;
  26. 		if (flag1 == true) break;
  27. 	}
  28. 	//ввод второго слова
  29. 	while (true){
  30. 		std::cout << "Введите второе слово, состоящее из букв 'а', 'г', 'ц', 'т' : ";
  31. 		std::cin >> word2;
  32. 		std::cout << word2 << std::endl;
  33. 		for (i = 0; i < word2.length(); i++)
  34. 			if (word2[i] == 'a' || word2[i] == 'r' || word2[i] == 'c' || word2[i] == 't')
  35. 				flag2 = true;
  36. 			else 
  37. 				flag2 = false;
  38. 		if (flag2 == true) break;
  39. 	}
  40. 	 int n = word1.length();
  41. 	 int m = word2.length();
  42. 	 int A[m][n];
  43. 	 int W[m][n];
  44. 	 //заполнение нулями и вывод массива А, если буквы не совпали
  45. 	 //и единицами на пересечениях совпавших букв
  46. 	std::cout << std::endl;
  47. 	for (j = 0; j < n; j++)
  48. 		std::cout << "{0} " << word1[j];
  49. 	std::cout << std::endl;
  50. 	for (i = 0; i < m; i++){
  51. 		std::cout << "{0} " << word2[i];
  52. 		for (j = 0; j < n; j++){
  53. 			if (word1[j] == word2[i]){
  54. 				A[i][j] = 1;
  55. 				std::cout << "1 "; 
  56. 			}
  57. 			else {
  58. 				A[i][j] = 0;
  59. 				std::cout << "0 "; 
  60. 		}}
  61. 		std::cout << std::endl;
  62. 	}
  63. 	//заполнение массива W:
  64. 	//заполнение первой строки
  65. 	for (j = 0; j < n; j++){
  66. 		if (flag3 == true || A[0][j] == 1){
  67. 			W[0][j] = 1;
  68. 			flag3 = true;
  69. 		}else 
  70. 			W[0][j] = 0;
  71. 	}
  72. 	// заполнение первого столбца
  73. 	for (i = 0; i < m; i++){
  74. 		if (flag4 == true || A[i][0] == 1){
  75. 			W[i][0] = 1;
  76. 			flag4 = true;
  77. 		}else
  78. 			W[i][0] = 0;
  79. 	}
  80. 	//дальнейшее заполнение
  81. 	for (i = 1; i < m; i++)
  82. 		for (j = 1; j < n; j++){
  83. 			if (A[i][j] == 0)
  84. 				if(W[i - 1][j] > W[i][j -1])
  85. 					W[i][j] = W[i - 1][j];
  86. 				else
  87. 					W[i][j] = W[i][j -1];
  88. 			else
  89. 				W[i][j] = W[i - 1][j - 1] + 1;
  90. 		}
  91. 	//вывод матрицы W
  92. 	std::cout << std::endl;
  93. 	for (j = 0; j < n; j++)
  94. 		std::cout << "{0} " << word1[j];
  95. 	std::cout << std::endl;
  96. 	for (i = 0; i < m; i++){
  97. 		std::cout << "{0} " << word2[j];
  98. 		for (j = 0; j < n; j++)
  99. 			std::cout << "{0} " << W[i][j];
  100. 		std::cout << std::endl;
  101. 	}
  102.  
  103. 	//поиск цепочки
  104. 	int lon = 0; //длина максимальной цепочки
  105. 	int lonx = 0; //координаты максимальной закрашенной буквы i
  106. 	int lony = 0;//координаты максимальной закрашенной буквы j
  107. 	for (i = m - 1; i > 0; i--){
  108. 		for (j = n - 1; j > 0; j--){
  109. 			if (A[i][j] == 1){
  110. 				lon = W[i][j];
  111. 				flag5 = true;
  112. 				lonx = i;
  113. 				lony = j;
  114. 				break;
  115. 			}
  116. 		}
  117. 		if (flag5) break;
  118. 	}
  119. 	std::cout << "Максимальная цепочка длиной {0}: " << lon << std::endl;
  120. 	rez += word2[lonx];
  121. 	for (int k = 0; k < lon - 1; k++){
  122. 		if (A[lonx - 1][lony - 1] == 1){
  123. 			lonx--;
  124. 			lony--;
  125. 	//rez += Convert.ToString(word2[lonx]);
  126. 			continue;
  127. 		}else
  128. 			for (i = lonx; i > lonx - 3 && flag; i--)
  129. 				for (j = lony; j > lony - 3 && flag; j--)
  130. 					if (i != lonx || j != lony)
  131. 						if (A[i][j] == 1){
  132. 							lonx = i;
  133. 							lony = j;
  134. 							flag = false;
  135. 						}
  136. 					rez += word2[lonx];
  137. 					flag = true;
  138. 	}
  139. 	std::reverse(rez.begin(),rez.end());
  140. 	std::cout << "Максимальная подпоследователность:" << rez;
  141. }
  142.  
Success #stdin #stdout 0.01s 5376KB
comments (?)
stdin
copy 
tatar
ratatac
stdout
copy 
Введите первое слово, состоящее из букв 'а', 'г', 'ц', 'т' : tatar
Введите второе слово, состоящее из букв 'а', 'г', 'ц', 'т' : ratatac

{0} t{0} a{0} t{0} a{0} r
{0} r0 0 0 0 1 
{0} a0 1 0 1 0 
{0} t1 0 1 0 0 
{0} a0 1 0 1 0 
{0} t1 0 1 0 0 
{0} a0 1 0 1 0 
{0} c0 0 0 0 0 

{0} t{0} a{0} t{0} a{0} r
{0} a{0} 0{0} 0{0} 0{0} 0{0} 1
{0} a{0} 0{0} 1{0} 1{0} 1{0} 1
{0} a{0} 1{0} 1{0} 2{0} 2{0} 2
{0} a{0} 1{0} 2{0} 2{0} 3{0} 3
{0} a{0} 1{0} 2{0} 3{0} 3{0} 3
{0} a{0} 1{0} 2{0} 3{0} 4{0} 4
{0} a{0} 1{0} 2{0} 3{0} 4{0} 4
Максимальная цепочка длиной {0}: 4
Максимальная подпоследователность:a
https://ideone.com/sEFbCq
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
secret

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!