Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- Longest common substring constrained by pattern
- #include <iostream>
- const std::string longestCommonSubstring(int, std::string const& s1, std::string const& s2, std::string const& s3);
- int main(void) {
- std::string s1="hello 5", s2="bolo 7", s3="lo 9sdf";
- std::cout << "Trying to get "lo 5", actual result: "" << longestCommonSubstring(5, s1, s2, s3) << '"';
- }
- const std::string longestCommonSubstring(int must_include, std::string const& s1, std::string const& s2, std::string const& s3) {
- std::string longest;
- for(size_t start=0, length=1; start + length <= s1.size();) {
- std::string tmp = s1.substr(start, length);
- if (std::string::npos != s2.find(tmp) && std::string::npos != s3.find(tmp)) {
- tmp.swap(longest);
- ++length;
- } else ++start;
- }
- return longest;
- }
- //find all pattern sequences
- N1 = findAllPatterns(s1, number);
- for i = 2 to n:
- for item in Ni-1:
- for match in findAllPatterns(si, nextPattern(item))
- Ni.add([item, (match, indexOf(match))]);
- //for all pattern sequences identify the max common substring
- maxCommonLength = 0;
- for sequence in Nn:
- temp = findLCS(sequence);
- if(length(temp[0]) > maxCommonLength):
- maxCommonLength = length(temp[0]);
- result = temp;
- return result;
- #include <iostream>
- #include <string>
- #include <sstream>
- #include <vector>
- typedef std::pair<std::pair<std::string, std::string>, std::pair<std::pair<std::string, std::string>, std::pair<std::string, std::string>>> pairStringTrio;
- typedef std::pair<std::string,std::pair<std::string,std::string>> stringPairString;
- stringPairString longestCommonSubstring(const pairStringTrio&);
- std::string strFindReplace(const std::string&, const std::string&, const std::string&);
- int main(void) {
- std::string s1= "6 HUMAN ACTIONb", s2="8 HUMAN ACTIONd", s3="10 HUMAN ACTIONf";
- pairStringTrio result = std::make_pair(std::make_pair(s1, "6"), std::make_pair(std::make_pair(s2, "8"), std::make_pair(s3, "10")));
- stringPairString answer = longestCommonSubstring(result);
- std::cout << '"' << answer.first << ""t"" << answer.second.first << ""t"" << answer.second.second << '"';
- }
- stringPairString longestCommonSubstring(const pairStringTrio &foo) {
- std::string longest;
- for(size_t start=0, length=foo.first.first.size()-1; start + length <= foo.first.first.size();) {
- std::string s1_tmp = foo.first.first.substr(start, length);
- std::string s2_tmp = strFindReplace(s1_tmp, foo.first.second, foo.second.first.second);
- std::string s3_tmp = strFindReplace(s1_tmp, foo.first.second, foo.second.second.second);
- if (std::string::npos != foo.second.first.first.find(s2_tmp) && std::string::npos != foo.second.second.first.find(s3_tmp)) {
- s1_tmp.swap(longest);
- ++length;
- } else ++start;
- }
- return std::make_pair(longest, std::make_pair(strFindReplace(longest, foo.first.second, foo.second.first.second), strFindReplace(longest, foo.first.second, foo.second.second.second)));
- }
- std::string strFindReplace(const std::string &original, const std::string& src, const std::string& dest) {
- std::string answer=original;
- for(std::size_t pos = 0; (pos = answer.find(src, pos)) != answer.npos;)
- answer.replace(pos, src.size(), dest);
- return answer;
- }
Add Comment
Please, Sign In to add comment