Eftersom två permutationer σ och π, Permutations Mönster problemet frågar om σ är en subpattern av π. Vi visar att problemet kan lösas i tid 2 O( 2 log ) ·n, där =... och n =.... Med andra ord, problemet är fast-parameter dragbar parameter av storleken på subpattern som finns. Vi introducerar en ny typ av nedbrytningar för permutationer och en motsvarande breddmått. Vi presenterar en linjär-tid algoritm som antingen finner σ som en subpattern av π, eller finner en nedbrytning av π vars bredd begränsas av en funktion av. Sedan visar vi hur man löser Permutations Mönster problemet i linjär tid om en avgränsad bredd sönderdelning ges i inmatningen.
I det exakta fallet visade Guillemot och Marx REF att ett ordermönster π av längd k kan hittas i en sekvens f av längd n i tid 2 O(k 2 log k) n; i synnerhet problemet med att hitta ordermönster är fast-parameterdragbar (i parameter k).
Finding small patterns in permutations in linear time
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}