ooks My library> ECE 270 home 12.3 P3-Ex1: Substrings E zyBooks catalog Help/FAQ

Question

ooks My library> ECE 270 home 12.3 P3-Ex1: Substrings E zyBooks catalog Help/FAQ Ja Compute and output the number of ways in which we can choose two identical non-overlapping substrings of a given string read from the user Constraints Read the string from the user. The given string will consist only of lowercase English letters (az). The Jength of the given string will be between 1 and 50, inclusive . Output your result using the following format %dn. Example 1 When the input is Output must be Example 2 When the input is aba Output must be Example 3 When the input is abab Output must be

Explanation / Answer

Dear,

Feel free to reach out if you have doubts. Please do rate if the answer was helpful. Thanks ----------------------------------------------------------------------------------------------------- Copyable Code: -----------------------------------------

Program:

// C++ program to find the longest repeated
// non-overlapping substring
#include<bits/stdc++.h>
using namespace std;

// Returns the longest repeating non-overlapping
int longestRepeatedSubstring(string str)
{
int n = str.length();
int LCSRe[n+1][n+1];

// Setting all to 0
memset(LCSRe, 0, sizeof(LCSRe));

string res; // To store result
int res_length = 0; // To store length of result

// building table in bottom-up manner
int i, index = 0;
for (i=1; i<=n; i++)
{
for (int j=i+1; j<=n; j++)
{
// (j-i) > LCSRe[i-1][j-1] to remove
// overlapping
if (str[i-1] == str[j-1] &&
LCSRe[i-1][j-1] < (j - i))
{
LCSRe[i][j] = LCSRe[i-1][j-1] + 1;

// updating maximum length of the
// substring and updating the finishing
// index of the suffix
if (LCSRe[i][j] > res_length)
{
res_length = LCSRe[i][j];
index = max(i, index);
}
}
else
LCSRe[i][j] = 0;
}
}

// If we have non-empty result, then insert all
// characters from first character to last
// character of string
if (res_length > 0)
for (i = index - res_length + 1; i <= index; i++)
res.push_back(str[i-1]);

return res.length();
}

// Driver program to test the above function
int main()
{
//string str = "abab";
  
string str;

cout << "Please enter your identical strings: ";
getline (cin, str);
  
cout << longestRepeatedSubstring(str);
  
  
return 0;
}

OUTPUT 1

Please enter your identical strings:   
abab   
2
  
...Program finished with exit code 0   
Press ENTER to exit console.

OUTPUT 2

Please enter your identical strings:   
aaabbbaaabbb   
6
  
...Program finished with exit code 0   
Press ENTER to exit console.   
  

Thank You.

Related Questions

Navigate

• Browse (All)
• Browse O
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.