用于查找2个字符串之间任意长度的所有共享子串的算法，然后计算字符串2中的出现次数？
我遇到了一个不同寻常的挑战，到目前为止，我无法确定最有效的攻击方法。
给定以下2个字符串作为示例，查找任意长度的2个字符串之间的所有共享子字符串，并计算字符串2中所有这些共享子字符串的出现次数。您的算法还需要能够计算之间的共享子字符串包含最大100MB或更大的字符串的文件。
例：
字符串1：ABCDE512ABC361EG51D
字符串2：ADE5AHDW4131EG1DG5C
给定这2个字符串，该算法将找到以下共享子串：A，C，D，E，5,1,3，G，DE，E5，EG，G5,1D，DE5,1EG
然后从这些共享的子串中，我们可以发现字符串2中每个子串的出现次数。
答：字符串2中出现2次
C：字符串2中出现1次
D：字符串2中出现3次
等等..
我用来解决这个问题的第一种方法是粗暴地强迫我使用2个嵌套for循环来计算公共共享子串 – 显然效率最低但是这是一种快速而肮脏的方式来了解预期的输出应该使用较小的测试输入和最慢的运行时间，大约2分钟来计算包含ascii字符串，大小为50kb的2个文件之间的所有常见共享子字符串。 将大小增加到1mb会导致这种情况急剧下降，因为计算此事件时必须进行大量的嵌套迭代。
下一个方法是使用树 – 看看我可以用多少内存来优化计算时间。 这种方法要快得多。 使用蛮力方法花费2分钟的两个50kb文件几乎是即时的。 对1mb文件运行速度非常快（秒）但是当我继续测试越来越大的文件大小时，由于树的大小，我很快就开始遇到内存问题。
注意：字符串文件只包含ASCII字符！
编辑：
我正在进一步升级，请看：
https://gist.github.com/braydo25/f7a9ce7ce7ad7c5fb11ec511887789bc
这是一个基于遍历输入串联的后缀数组的C实现，借助最长的公共前缀数组。 您可以将编程竞争等级（O（n log ^ 2 n））后缀数组实现替换为实数（O（n）或O（n log n）），以获得较大的性能提升。 （编辑：这样做，其他一些变化反映了提问者的新要求： https ： //github.com/eisenstatdavid/commonsub 。）
#include #include #include #include #include typedef int_fast32_t I32; #define Constrain(expression) _Static_assert(expression, #expression) Constrain(CHAR_BIT == 8); #define InputMaxBytes 80000000 Constrain(InputMaxBytes <= (INT_LEAST32_MAX - 2) / 2); #define MaxLen (2 * InputMaxBytes + 2) Constrain(MaxLen <= INT_FAST32_MAX / 2); static I32 Len; static I32 Begin2; static signed char Buf[MaxLen]; static int_least32_t SufArr[MaxLen]; static int_least32_t SufRank[MaxLen]; static int_least32_t NewRank[MaxLen]; static int_least32_t *const LongCommPre = NewRank; // aliased to save space static uint_least64_t Bitmap2[(MaxLen >> 6) + 1]; static int_least32_t SparseCount2[(MaxLen >> 6) + 1]; static int_least32_t *const Stack = SufRank; // aliased to save space static void Slurp(const char *filename) { FILE *stream = fopen(filename, "r"); if (stream == NULL) goto fail; I32 n = fread(Buf + Len, sizeof *Buf, InputMaxBytes + 1, stream); if (ferror(stream)) goto fail; if (n > InputMaxBytes) { fprintf(stderr, "%s: file is too large; increase InputMaxBytes\n", filename); exit(EXIT_FAILURE); } for (I32 i = 0; i < n; i++) { if (Buf[Len + i] < 0) { fprintf(stderr, "%s: file contains non-ASCII byte at offset %" PRIdFAST32 "\n", filename, i); exit(EXIT_FAILURE); } } Len += n; if (fclose(stream) == EOF) goto fail; return; fail: perror(filename); exit(EXIT_FAILURE); } static I32 Radix; static int CompareRankPairs(const void *iPtr, const void *jPtr) { I32 i = *(const int_least32_t *)iPtr; I32 j = *(const int_least32_t *)jPtr; if (SufRank[i] < SufRank[j]) return -1; if (SufRank[i] > SufRank[j]) return 1; I32 iRank = i + Radix < Len ? SufRank[i + Radix] : -2; I32 jRank = j + Radix < Len ? SufRank[j + Radix] : -2; if (iRank < jRank) return -1; if (iRank > jRank) return 1; return 0; } static void BuildSuffixArray(void) { for (I32 i = 0; i < Len; i++) { SufArr[i] = i; SufRank[i] = Buf[i]; } for (Radix = 1; true; Radix *= 2) { qsort(SufArr, Len, sizeof *SufArr, CompareRankPairs); NewRank[0] = 0; for (I32 i = 1; i < Len; i++) { NewRank[i] = CompareRankPairs(&SufArr[i - 1], &SufArr[i]) == 0 ? NewRank[i - 1] : NewRank[i - 1] + 1; } for (I32 i = 0; i < Len; i++) { SufRank[SufArr[i]] = NewRank[i]; } if (NewRank[Len - 1] == Len - 1) break; } I32 lenCommPre = 0; for (I32 i = 0; i < Len; i++) { if (SufRank[i] == Len - 1) { LongCommPre[SufRank[i]] = -1; continue; } while (Buf[i + lenCommPre] == Buf[SufArr[SufRank[i] + 1] + lenCommPre]) { lenCommPre++; } LongCommPre[SufRank[i]] = lenCommPre; if (lenCommPre > 0) lenCommPre--; } } static I32 PopCount(uint_fast64_t x) { I32 v = 0; while (x != 0) { x &= x - 1; v++; } return v; } static void BuildCumCount2(void) { for (I32 i = 0; i < Len; i++) { if (SufArr[i] >= Begin2) { Bitmap2[i >> 6] |= UINT64_C(1) << (i & 63); SparseCount2[i >> 6]++; } } for (I32 i = 0; i < (Len >> 6); i++) { SparseCount2[i + 1] += SparseCount2[i]; } } static I32 CumCount2(I32 i) { return SparseCount2[i >> 6] - PopCount(Bitmap2[i >> 6] >> (i & 63)); } static void FindCommonStrings(void) { I32 lenCommPre = -1; for (I32 i = 0; i < Len; i++) { while (lenCommPre > LongCommPre[i]) { I32 begin = Stack[lenCommPre]; I32 end = i + 1; I32 count2 = CumCount2(end) - CumCount2(begin); if (count2 > 0 && count2 < end - begin && lenCommPre > 0) { printf("%" PRIdFAST32 "\t%.*s\n", count2, (int)lenCommPre, Buf + SufArr[begin]); } lenCommPre--; } while (lenCommPre < LongCommPre[i]) { lenCommPre++; Stack[lenCommPre] = i; } } } int main(int argc, char *argv[]) { if (argc != 3) { fputs("usage: commonsub needle haystack\n", stderr); exit(EXIT_FAILURE); } Len = 0; Slurp(argv[1]); Buf[Len] = -1; Len++; Begin2 = Len; Slurp(argv[2]); Buf[Len] = -2; // sentinel BuildSuffixArray(); if (false) { for (I32 i = 0; i < Len; i++) { printf("%" PRIdFAST32 "\t%" PRIdLEAST32 "\t%" PRIdLEAST32 "\t%.*s\n", i, SufArr[i], LongCommPre[i], (int)(Len - SufArr[i]), Buf + SufArr[i]); } } BuildCumCount2(); FindCommonStrings(); }
以下是一些代码，说明了我在上面的评论中提出的想法。 虽然它是可运行的C ++代码，但在使用的数据结构肯定不是最优的意义上它是更多的伪代码，但它们允许清晰地查看算法。
struct Occurrence { //The vectors contain indices to the first character of the occurrence in ... std::vector s1; // ... string 1 and ... std::vector s2; // ... string 2. }; int main() { //If you cannot load the entire strings in memory, a memory-mapped file might be //worth considering std::string s1 = "ABCDE512ABC361EG51D"; std::string s2 = "ADE5AHDW4131EG1DG5C"; //These vectors store the occurrences of substrings for the current and next length std::vector occurrences, nextOccurrences; int length = 1; std::map occurrenceMap; //Initialize occurrences for (int i = 0; i < s1.length(); ++i) occurrenceMap[s1[i]].s1.push_back(i); for (int i = 0; i < s2.length(); ++i) occurrenceMap[s2[i]].s2.push_back(i); for (auto& pair : occurrenceMap) { if (pair.second.s1.size() > 0 && pair.second.s2.size() > 0) occurrences.push_back(std::move(pair.second)); } do { nextOccurrences.clear(); std::cout << "Length " << length << std::endl; for(auto& o : occurrences) { std::cout << std::string(s1.c_str() + o.s1[0], length) << " occurred " << o.s1.size() << " / " << o.s2.size() << " times." << std::endl; //Expand the occurrence occurrenceMap.clear(); for (auto p : o.s1) { if (p + length < s1.length()) occurrenceMap[s1[p + length]].s1.push_back(p); } for (auto p : o.s2) { if (p + length < s2.length()) occurrenceMap[s2[p + length]].s2.push_back(p); } for (auto& pair : occurrenceMap) { if (pair.second.s1.size() > 0 && pair.second.s2.size() > 0) nextOccurrences.push_back(std::move(pair.second)); } } ++length; std::swap(occurrences, nextOccurrences); } while (!occurrences.empty()); return 0; }
输出：
Length 1 1 occurred 3 / 3 times. 3 occurred 1 / 1 times. 5 occurred 2 / 2 times. A occurred 2 / 2 times. C occurred 2 / 1 times. D occurred 2 / 3 times. E occurred 2 / 2 times. G occurred 1 / 2 times. Length 2 1D occurred 1 / 1 times. 1E occurred 1 / 1 times. DE occurred 1 / 1 times. E5 occurred 1 / 1 times. EG occurred 1 / 1 times. G5 occurred 1 / 1 times. Length 3 1EG occurred 1 / 1 times. DE5 occurred 1 / 1 times.
初始化期间将使用最多的内存，因为两个输入字符串的每个字符都有一个条目。 如果您知道字符串的大致长度，则可以选择比size_t更合适的索引数据类型。 所需的内存量按输入大小的顺序排列。 因此，对于普通计算机，两个100 MB的文件应该没问题。 在初始化之后（更具体地说，在循环的第一次迭代之后），大多数这些数据将被删除，因为不再需要它们。
在看了两个字符串并稍微考虑了这一点后，我已经在脑海中完成了这个过程，现在我将把它翻译成步骤。
String 1: ABCDE512ABC361EG51D // S1 String 2: ADE5AHDW4131EG1DG5C // S2
当我考虑这个时，我们可以比较从S1到S2的字符和/或子串，同时跟踪事件的发生。
S1[0] = 'A' compare S2[0] = 'A' = true : found A in S2 at location 0 S1[0] = 'A' compare S2[1] = 'D' = false S1[0] = 'A' compare S2[2] = 'E' = false S1[0] = 'A' compare S2[3] = '5' = false S1[0] = 'A' compare S2[4] = 'A' = true : found A in S2 at location 4 S1[0] = 'A' compare S2[5] = 'H' = false S1[0] = 'A' compare S2[6] = 'D' = false S1[0] = 'A' compare S2[7] = 'W' = false S1[0] = 'A' compare S2[8] = '4' = false S1[0] = 'A' compare S2[9] = '1' = false S1[0] = 'A' compare S2[10] = '3' = false S1[0] = 'A' compare S2[11] = '1' = false; S1[0] = 'A' compare S2[12] = 'E' = false; S1[0] = 'A' compare S2[13] = 'G' = false; S1[0] = 'A' compare S2[14] = '1' = false; S1[0] = 'A' compare S2[15] = 'D' = false; S1[0] = 'A' compare S2[16] = 'G' = false; S1[0] = 'A' compare S2[17] = '5' = false; S1[0] = 'A' compare S2[18] = 'C' = false; // End of First Search - Occurrences of 'A' in S2 is 2 at locations {0,4} // Next Iteration String 1: ABCDE512ABC361EG51D // S1 String 2: ADE5AHDW4131EG1DG5C // S2 // Repeat this for all single characters Of S1 against S2 'A' in S2 = 2 at {0,4} 'B' in S2 = 0 'C' in S2 = 1 at {18} 'D' in S2 = 3 at {1,6,15} 'E' in S2 = 2 at {2,12} '5' in S2 = 2 at {3,17} '1' in S2 = 3 at {9,11,14} '2' in S2 = 0 'A' Already Found Above Skip 'B' Already Found Above Skip 'C' Already Found Above Skip '3' in S2 = 1 at {10} '6' in S2 = 0 '1' Already Found Above Skip 'E' Already Found Above Skip 'G' in S2 = 2 at {13, 16} '5' Already Found Above Skip '1' Already Found Above Skip 'D' Already Found Above Skip
这将结束用于执行所有单个字符的第一组迭代，并且您可以看到我们还构建了一个列表和一组或多组不仅出现而且还有它们的位置，我们可以将它们存储以供将来引用。 因此，如果我们开始在S2中搜索S1 [0＆1]，我们知道S2中不存在S1 [1]，因此我们可以打破并且不需要沿着该链断开，因为我们可以突破该分支我们也可以跳过S1 [1＆… N]并直接移动到S1 [2]，我们知道S1 [2]只有1次出现，S2位于{18}是’C’，是字符串的结尾所以不需要查找S1 [2＆… N]所以我们可以跳过这个并移动到S1 [3]即’D’，我们知道它确实存在于S2中在{1,6,15}所以现在我们可以从S2 [1＆… N]开始搜索S1 [3＆… N]，然后再次对S1进行相同的搜索[3＆… N]从S2 [6＆… N]开始，最后再次开始S2 [15＆… N]，然后我们现在找到所有在S2中以D开头的子字符串，我们可以保存它们的出现次数; 但是，我们确实希望找到两者之间最长的子串。 最长的子字符串是“DE5”并且只有一次出现，但是从这里我们还找到了子字符串“DE”和“E5”，所以我们也可以在这一点上搜索它们然后我们找到它们每次发生一次。 我们只是重复这个过程。 一开始需要很长时间，但是遍历字符串的次数越多，因为消除已经发现的事件以及跳过S2中未找到的S1子字符串，它的工作速度就越快。
这是我在不使用任何代码或编程语义的情况下采用的逻辑方法，因为它只是逻辑上执行此操作的基本算法。 现在，将其置于函数和容器中以编写它的源代码实现成为一个决心。
编辑 – 正如评论中关于这个与另一个答案的区别以及时间和空间复杂性的问题在这里是我的算法的一个版本，第一次搜索单个字符并创建位置表，如果它们存在于第二个串。 类中存储的向量包含S2中S1中的每个唯一字符。 然后可以使用它来帮助查找更长的子串。
// C++ - The user asked for this in C but I haven't used C in nearly 10 years so this is my version of it in C++ :( #include #include class SubStringSearch { private: std::string S1; std::string S2; struct SubstringResult { std::string substring; bool found; std::vector positions; SubstringResult(){} SubstringResult( const std::string& substringIn, bool foundIn, std::vector positionsIn ) : substring( substringIn ), found( foundIn ), positions( positionsIn ) {} }; std::vector results; public: SubStringSearch( const std::string& s1, const std::string& s2 ) : S1( s1 ), S2( s2 ) {} void compareStringsFirstPass(); std::vector findLocations( const std::string& str, char findIt ); void printResults() const; }; std::vector SubStringSearch::findLocations( const std::string& str, char findIt ) { std::vector locations; for ( unsigned i = 0; i < str.size(); ++i ) { if ( str[i] == findIt ) { locations.push_back( i ); } } return locations; } void SubStringSearch::compareStringsFirstPass() { std::vector positions; std::string sub; bool alreadyFound = false; for ( unsigned idx = 0; idx < S1.size(); ++idx ) { sub = S1[idx]; if ( idx > 0 ) { for ( unsigned u = 0; u < results.size(); ++u ) { if ( sub == results[u].substring ) { alreadyFound = true; break; } } } // Added An If Else Here To Reduce Unneeded Calls To findLocations() if ( alreadyFound ) { alreadyFound = false; continue; } else { positions = findLocations( S2, S1[idx] ); } if ( positions.size() > 0 && !alreadyFound ) { results.push_back( SubstringResult( sub, true, positions ) ); } else if ( !alreadyFound ) { positions.clear(); results.push_back( SubstringResult( sub, false, positions ) ); } positions.clear(); alreadyFound = false; } } void SubStringSearch::printResults() const { for ( unsigned u = 0; u < results.size(); ++u ) { if ( results[u].found ) { std::cout << results[u].substring << " found in S2 at " << std::setw(2); for ( unsigned i = 0; i < results[u].positions.size(); ++i ) { std::cout << std::setw(2) << results[u].positions[i] << " "; } std::cout << std::endl; } } } int main() { std::string S1( "ABCDE512ABC361EG51D" ); std::string S2( "ADE5AHDW4131EG1DG5C" ); SubStringSearch searchStrings( S1, S2 ); searchStrings.compareStringsFirstPass(); std::cout << "break point"; return 0; } // main
在最后一个打印行上放置一个断点，然后进入您的本地人或MSVC中的汽车的调试器或您的编译器/调试器版本的等效项，并查看类的成员变量std ::的内容向量，你会看到S1中的字符和附加到它的字符将是一个bool标志，如果它被找到或不与每个位置的std :: vector。 因此，如果标志为假，则向量大小应为0，反之亦然，如果向量大小> 0，则标志应为真; 位置向量的大小也是第二个字符串中该字符的计数或出现次数，这使得这很好，因为我们不必计算任何其他我们可以从向量本身得到的。
现在这不是完整或完整的算法，因为这只是在构建所需的表并跳过已经找到的内容时，第一次执行字符串1的每个单个字符并查看字符串2。 如果他们选择完成算法的其余部分，那将由OP构建。 如果我碰巧在不久的将来找到一些空闲时间，我可以继续完成整个算法。
根据我的理解，将字符串分解为所有可能的子字符串本身就是O（n * n）操作。
abcd ==== a,b,c,d ab,bc,cd abc,bcd abcd ************************ abcdefgh ======== a,b,c,d,e,f,g,h ab,bc,cd,de,ef,fg,gh abc,bcd,cde,def,efg,fgh abcd,bcde,cdef,defg,efgh abcde,bcdef,cdefg,defgh abcdef,bcdefg,cdefgh abcdefg,bcdefgh abcdefgh
因此，它看起来不像线性时间的解决方案。
更实际地解决它，从Java语言的角度来看，你必须首先将其分解并将其存储在一个集合或一个映射中（map可以将子字符串作为键，并将出现的次数作为count）。
然后重复第二个字符串的步骤。
然后，您可以迭代第一个，检查第二个字符串的映射中是否存在该条目，并同时增加该子字符串的出现次数。
如果您使用’C’，那么您可以尝试对子字符串数组进行排序，然后使用二进制搜索来查找匹配项（同时使用二维数组来跟踪字符串和出现次数）。
你说你有一个跑得快的树的方法。 你介意发布样本以便你如何使用树吗？ 是用于表示子字符串还是帮助生成子字符串？