METHOD FOR FINDING DYNAMIC LONGEST COMMON NONSUPERSTRING BASED ON PREFIX GRAPH MODEL

摘要

PURPOSE: A dynamic LCNSS searching method based on a prefix graph model is provided to rapidly and efficiently search LCNSS by modifying a peak point and a main point corresponding to a letter string which is added or deleted to the combination of a forbidden letter string. CONSTITUTION: A prefix graph which is generated by a forbidden string set is reconfigured by generating a peak point and a main point corresponding to the letter string which is added to the forbidden letter string set(S100). A LCNSS(Longest Common Non-Superstring) corresponding to the longest letter string is searched by using the reconfigured prefix graph(S300). The prefix graph is reconfigured by searching a peak point corresponding to the added letter string in the prefix graph. If the peak point corresponding to the added letter string does not exists in the prefix graph, the peak point and the main point corresponding to the added letter string is generated to the prefix graph.