{'fraction_non_alphanumeric': 0.024370430544272948, 'fraction_numerical': 0.0, 'mean_word_length': 5.129353233830845, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
An Improved Divide-and-Conquer Algorithm for Finding Top-k Longest Common Subsequence

Finding the multiple longest common subsequence(MLCS) and other derived problems belong to NP-hard problems, which is especially used in comparing files, comparison of DNA and protein sequences. An efficient method applicable to solve top-k MLCS has been proposed in this paper. It implements to quickly find the LCS of all k sequences in a given n sequences with less space occupation. To reduce retrieval time, SF_MLCS algorithm was proposed firstly, which improve the hash storage structure of the direct successor nodes of matching points in irredundant common subsequence graph. On the basis of it, introducing the divide-and-conquer strategy, DC_MLCS algorithm was proposed, which divided the whole MLCS problems into several subproblems, to meet the requirement for longer or long-scale sequences. At the same time, in the process of solving the direct successor nodes, the number of sequences satisfying the conditions was limited to change the structure of matching points, and the DC_MLCS algorithm was extended to the DC_MLCS+ algorithm of finding top-k LCS. Experiments based on real datasets verify the efficiency of our algorithm.