Substrings-3 Input file: stdin Output file: stdout Time limit: 2 sec Memory limit: 256…
- User
Substrings-3 Input file: stdin
Output file: stdout
Time limit: 2 sec
Memory limit: 256 mb
You are given strings of lowercase Latin letters. Find their longest common substring.
Input The first line contains a single integer ().
Next lines contain given (each string is at least and at most characters long), one per line.
Output The sole line of the output should contain the longest common substring.
Examples Input 1
3 abacaba mycabarchive acabistrue Output 1: cab
- Assistant
To solve the problem of finding the longest common substring among multiple strings, we can use a strategy that combines binary search with substring checking, leveraging the fact that the number of strings (k) is relatively small (up to 10). Here’s a breakdown of how we can achieve this effectively:
Steps for the Solution:
-
Binary Search Setup:
- We'll use binary search on the length of the common substring we want to test, from 0 up to the length of the shortest string provided (since the longest common substring cannot be longer than any of the strings).
-
Checking for Common Substring:
- For a given length
midduring our binary search, we will extract all substrings of that length from the first string and then check if any of these substrings exist in all the other strings.
- For a given length
-
Efficiency:
- Since extracting all substrings and checking can be computationally expensive, we can optimize the substring checking using a set to store the first string's substrings and then check each of these against the other strings.
-
Keep Track of the Longest Common Substring:
- Throughout this process, maintain the longest common substring found when checking each middle length during the binary search.
Implementation
Here is the Python implementation based on the described strategy:
def has_common_substring_of_length(strs, length): if length == 0: return True, '' first_string = strs[0] seen = set(first_string[i:i + length] for i in range(len(first_string) - length + 1)) for s in strs[1:]: found = False for i in range(len(s) - length + 1): if s[i:i + length] in seen: found = True common_substring = s[i:i + length] break if not found: return False, '' return True, common_substring def longest_common_substring(strs): left, right = 0, min(len(s) for s in strs) longest_substring = '' while left <= right: mid = (left + right) // 2 found, substring = has_common_substring_of_length(strs, mid) if found: if mid > len(longest_substring): longest_substring = substring left = mid + 1 else: right = mid - 1 return longest_substring def main(): import sys input = sys.stdin.read data = input().splitlines() k = int(data[0]) # The number of strings strings = data[1:k + 1] # The strings result = longest_common_substring(strings) print(result)Explanation of the Code:
-
has_common_substring_of_length: This function checks if there is a common substring of a specific length across all strings. It generates all possible substrings of that length from the first string and checks them against the others.
-
longest_common_substring: This orchestrates the binary search mechanism over the lengths and keeps track of the longest common substring found.
Input and Output:
The function reads from standard input and writes the result (the longest common substring) to standard output. This function will work efficiently within the provided constraints.
Conclusion:
Using binary search significantly reduces the number of checks we need to make, and by leveraging sets, we can check for commonality among the substrings efficiently, ensuring that we stay within the problem's limits. This approach is structured to handle edge cases effectively, such as when there is only one string or when the strings have no common substrings.
-
- User
in c++
- Assistant
Sure! Below is the equivalent C++ implementation for finding the longest common substring among multiple strings using binary search combined with substring checking:
#include <iostream> #include <vector> #include <string> #include <unordered_set> using namespace std; // Function to check if there's a common substring of a specific length bool has_common_substring_of_length(const vector<string>& strs, int length, string& common_substr) { if (length == 0) { common_substr = ""; return true; } unordered_set<string> seen; const string& first_string = strs[0]; // Store all substrings of the given length from the first string for (int i = 0; i <= first_string.size() - length; i++) { seen.insert(first_string.substr(i, length)); } // Check these substrings against the other strings for (size_t j = 1; j < strs.size(); ++j) { bool found = false; const string& s = strs[j]; for (int i = 0; i <= s.size() - length; i++) { string substring = s.substr(i, length); if (seen.count(substring)) { found = true; common_substr = substring; // Store the first found common substring break; } } if (!found) { return false; // If any string doesn't have the substring, return false } } return true; // All strings contained at least one of the substrings of this length } // Function to find the longest common substring string longest_common_substring(const vector<string>& strs) { int left = 0, right = 0; // Find the length of the shortest string for (const string& str : strs) { right = max(right, static_cast<int>(str.size())); } right = strs.empty() ? 0 : min(right, static_cast<int>(strs[0].size())); string longest_substring = ""; // Binary search for the maximum length of the common substring while (left <= right) { int mid = (left + right) / 2; string common_substr; if (has_common_substring_of_length(strs, mid, common_substr)) { longest_substring = common_substr; // Update the longest found left = mid + 1; // Try for a longer length } else { right = mid - 1; // Decrease the length } } return longest_substring; } int main() { int k; cin >> k; // Read the number of strings vector<string> strings(k); // Read the k strings for (int i = 0; i < k; i++) { cin >> strings[i]; } // Get the longest common substring string result = longest_common_substring(strings); // Output the result cout << result << endl; return 0; }Explanation of the Code:
-
has_common_substring_of_length:
- This function checks if there is a common substring of a specific length across all strings. It uses an unordered set to store all possible substrings of that length from the first string and then checks these substrings against the remaining strings.
-
longest_common_substring:
- This function performs a binary search on the possible lengths of the longest common substring, utilizing the helper function to check for common substrings of the current midpoint length.
-
Main Function:
- Reads the number of strings and the strings themselves from standard input, and then calls the logic to find the longest common substring, which it outputs to standard output.
Usage
You can compile this code using a C++ compiler and run it while providing input in the specified format. The program will print out the longest common substring found in the provided strings.
This C++ solution efficiently handles the problem constraints and provides a robust method for finding the solution.
-