A METHOD FOR FINDING CONSISTENT SUPERSTRINGS USING DIRECTED GRAPHS

摘要

PURPOSE: A CSS search method using a generated graph is provided to effectively search the CSS by generating and using the graph for CSS search based on an Aho-Corasick algorithm. CONSTITUTION: A CSS(Consistent Superstring) graph which is a graph is comprised by generating determistic finite automaton which expresses the letter string combination and removing the vertex and trunk line corresponding to all letter string of all sound based on an Aho-Corasick algorithm(S100). A SCSS(Shortest Consistent Superstring) obtains the shortest path including the character string of all amounts based on the CSS graph and is calculated(S200). A LCSS(Longest Consistent Superstring) obtains the longest path including the character string of all amounts based on the SCSS graph and is calculated(S300).