गतिशील पैटर्न के साथ स्ट्रिंग मिलान

इस कार्य में, हम स्ट्रिंग मिलान समस्या के एक प्राकृतिक भिन्नता से निपटते हैं, गतिशील पैटर्न के मामले में, अर्थात्, एक स्थिर पाठ T और एक पैटर्न P दिया गया है, हम पैटर्न में वर्ण जोड़ने और हटाने का समर्थन करना चाहते हैं, और प्रत्येक ऑपरेशन के बाद यह गणना करना चाहते हैं कि यह पाठ में कितनी बार occurs होता है। हम Suffix Arrays का उपयोग करते हुए एक सरल और व्यावहारिक एल्गोरिदम दिखाते हैं जो O (|T|) अद्यतन समय प्राप्त करता है, O (|T|) पूर्व-प्रक्रमण समय के बाद। हम यह दिखाते हैं कि कैसे हमारे समाधान को उप-पाठ हटाने, विनिमय (एक उप-पाठ को पैटर्न की दूसरी स्थिति में स्थानांतरित करना), और कॉपी (एक उप-पाठ को कॉपी करना और इसे एक विशिष्ट स्थिति में चिपकाना) का समर्थन करने के लिए विस्तारित किया जा सकता है, समान समय जटिलताओं में। हमारा समाधान एक ऑनलाइन पाठ (पाठ के एक छोर पर वर्ण जोड़ना) का समर्थन करने के लिए भी विस्तारित किया जा सकता है, समान अमॉर्टाइज़्ड बाउंड बनाए रखते हुए।