Problema: 1237
Enunciado:
Encontre a maior substring comum entre as duas strings informadas. A substring pode ser qualquer parte da string, inclusive ela toda. Se não houver subseqüência comum, a saída deve ser “0”. A comparação é case sensitive ('x' != 'X').
Linguagem: C++
Neste problema foi feita a proprosta de duas soluções. A primeira foi feita utilizando apenas um vetor para armazenar os dados e na segunda uma matriz. A solução do vetor é menos eficiente por exigir mais comparações, mas é capaz de ter um melhor aproveitamento de recursos computacionais. Note que este problema não é igual ao LCS porque a substring precisa ser contínua.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 | #include <iostream> using namespace std; int lcs_adapted(string str1, string str2){ int m = str1.length(); int n = str2.length(); int Results[m + 1][n + 1]; int max = 0; for (int i = 0; i <= m; i++) { for (int j = 0; j <= n; j++) { if (i == 0 || j == 0) Results[i][j] = 0; else if (str1[i-1] == str2[j-1]) { Results[i][j] = Results[i-1][j-1] + 1; if(max < Results[i][j]) max = Results[i][j]; } else Results[i][j] = 0; } } return max; } int main() { string str1, str2; while(getline(cin,str1)){ getline(cin,str2); cout << lcs_adapted(str1, str2) << endl; } return 0; } |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 | #include <iostream> using namespace std; int lcs_adapted(string str1, string str2){ int m = str1.length(); int n = str2.length(); int Results[m + 1][n + 1]; int max = 0; for (int i = 0; i <= m; i++) { for (int j = 0; j <= n; j++) { if (i == 0 || j == 0) Results[i][j] = 0; else if (str1[i-1] == str2[j-1]) { Results[i][j] = Results[i-1][j-1] + 1; if(max < Results[i][j]) max = Results[i][j]; } else Results[i][j] = 0; } } return max; } int main() { string str1, str2; while(getline(cin,str1)){ getline(cin,str2); cout << lcs_adapted(str1, str2) << endl; } return 0; } |
