स्ट्रिंग का पता लगाएं/एल्गोरिथ्म

Question

बदलें मैं विभिन्न शब्दों के लिए एक स्ट्रिंग खोज करने के लिए, जब मैं एक मिल जाए, मैं 3 भागों (छोड़ दिया, मैच, दाएं), मिलान वाला पाठ में उस बिंदु पर स्ट्रिंग विभाजित करना चाहते हैं सक्षम होने के लिए चाहते हैं बाहर रखा जाएगा, और प्रक्रिया नई स्ट्रिंग बाएं + दाएं के साथ जारी रहेगी।

अब, एक बार मैं अपने सभी मैचों किया है, मैं बात वे हटा दिया गया पर मिलान किया शब्द (या उनके लिए एक प्रतिस्थापन) पुन: लगाने प्रक्रिया को उल्टा करने की जरूरत है। मैंने कभी भी मेरी किसी भी खोज में जो कुछ भी नहीं खोजा है, मैंने सोचा कि मैं यहां SO इनपुट पर पूछूंगा।

कृपया मुझे बताएं कि क्या इस प्रश्न को और विवरण चाहिए।

बीटीडब्ल्यू - फिलहाल, मेरे पास एक बहुत ही खराब एल्गोरिदम है जो एक अद्वितीय स्ट्रिंग टोकन के साथ मिलान किए गए टेक्स्ट को प्रतिस्थापित करता है, और फिर सभी मैचों के बाद उचित मिलान के लिए प्रतिस्थापन टेक्स्ट के साथ टोकन को प्रतिस्थापित करता है।

one two three four five six 

मैच "तीन" foo के साथ बदलें (याद हम तीन पाया, और जहाँ हम यह पाया)

one two four five six 
     | 
    three 

मैच "दो से चार" और यह को रोकने:

यह लक्ष्य है किसी भी चीज़ से मिलान (स्पष्टता के लिए संपादित)

one five six 
    | 
two four 
     | 
    three 

इस बिंदु पर, आप उदाहरण के लिए मेल नहीं खा सकते हैं " ई दो "

सभी मैचों

पाए गए हैं, अब उनके प्रतिस्थापन वापस रख (उलटे क्रम में)

one two four five six 
     | 
    three 


one two foo four five six 

फ़ायदा क्या है? एक मैच के प्रतिस्थापन पाठ को किसी अन्य पैटर्न से मिलान करने से रोकना।

(सभी पैटर्न एक ही समय में और है कि संसाधित किया जाता है हर स्ट्रिंग के लिए एक ही क्रम में चलाए जा रहे हैं) मुझे यकीन है कि भाषा मामलों नहीं कर रहा हूँ, लेकिन मैं इस मामले में लुआ उपयोग कर रहा हूँ।

मैं फिर से प्रयास करने की कोशिश करूंगा, मेरे पास पैटर्न की एक सूची है जो मैं किसी दिए गए स्ट्रिंग में ढूंढना चाहता हूं, अगर मुझे कोई मिल जाए, तो मैं स्ट्रिंग के उस भाग को हटाना चाहता हूं, इसलिए यह किसी और चीज से मेल नहीं खाता है, लेकिन मैं चाहता हूं जहां मैं यह पाया का ट्रैक रखने के तो मैं प्रतिस्थापन पाठ वहाँ सम्मिलित कर सकते हैं एक बार मैं पैटर्न

यहाँ एक संबंधित सवाल है की मेरी सूची से मेल करने की कोशिश कर किया हूँ:

Shell script - search and replace text in multiple files using a list of strings

Answer 1

आपका एल्गोरिदम विवरण अस्पष्ट है। कोई सटीक नियम नहीं है जहां निकाले गए टोकन को दोबारा डाला जाना चाहिए।

यहाँ एक उदाहरण है:

एक:

1. ढूँढें 'तीन' 'एक दो तीन चार पांच से छह' में

2. इन दोनों में से किसी एक को चुनें परिणाम के रूप में प्राप्त करने के लिए 'foo बार' । 'एक' 'को' फू 'और' चार पांच छः 'के साथ' बार '

   बी के साथ बदलें। 'Foo बार'

3. सम्मिलित 'तीन' चरण 2 जिसके परिणामस्वरूप स्ट्रिंग 'foo बार'

चरण 3 पर करता है 'तीन' में वापस चला जाता है इससे पहले कि 'इससे ​​बदलें' एक दो से चार पांच से छह ' बार 'या उसके बाद?

एक बार जब आप पुन: सम्मिलित करने के लिए स्पष्ट नियमों के साथ आते हैं, तो आप आसानी से एल्गोरिदम को रिकर्सिव विधि के रूप में या प्रतिस्थापन स्टैक के साथ एक पुनरावृत्ति विधि के रूप में कार्यान्वित कर सकते हैं।

Answer 2

की संरचना को देखते हुए समस्या, मैं शायद एक बाइनरी पेड़ के आधार पर एक एल्गोरिदम कोशिश करेंगे।

Answer 3

स्यूडोकोड:

for(String snippet in snippets) 
{ 
    int location = indexOf(snippet,inputData); 
    if(location != -1) 
    { 
     // store replacement text for a found snippet on a stack along with the 
     // location where it was found 
     lengthChange = getReplacementFor(snippet).length - snippet.length; 
     for each replacement in foundStack 
     { 
      // IF the location part of the pair is greater than the location just found 
      //Increment the location part of the pair by the lengthChange to account 
      // for the fact that when you replace a string with a new one the location 
      // of all subsequent strings will be shifted 
     } 

     //remove snippet 
     inputData.replace(snippet, ""); 
    } 
} 

for(pair in foundStack) 
{ 
    inputData.insert(pair.text, pair.location); 
} 

यह मूलतः सिर्फ वास्तव में क्या कर रहा है के रूप में आप अपनी समस्या का वर्णन में कहा। एल्गोरिदम के माध्यम से कदम, उस स्थान के साथ सबकुछ एक स्टैक पर डालकर जो मिला था। आप एक स्टैक का उपयोग करते हैं ताकि जब आप दूसरे छमाही में फिर से सम्मिलित हों, तो यह रिवर्स ऑर्डर में होता है ताकि संग्रहित "स्थान" इनपुट स्ट्रिंग की वर्तमान स्थिति पर लागू हो।

टिप्पणीकार की आलोचना के लिए संभावित सुधार के साथ संपादित किया गया।क्या आपकी आलोचनाओं के लिए पहले एक खाते में ब्लॉक के लिए टिप्पणी की गई है, या यह अभी भी कुछ परिदृश्यों में छोटी है?

Answer 4

आप जो करना चाहते हैं वह एक दूसरी स्ट्रिंग है जो आउटपुट स्टोर करती है। आप इनपुट पर संसाधित करते हैं और पैटर्न पर खोज करते हैं। यदि कोई मिलान पैटर्न नहीं मिला है, तो कोई प्रतिस्थापन नहीं होता है, इसलिए आप केवल उन वर्णों को जोड़ते हैं जिन्हें आप सीधे आउटपुट पर पढ़ते हैं। यदि पैटर्न पाया गया है, तो प्रतिस्थापन स्ट्रिंग को आउटपुट पर जोड़ें। क्योंकि आप हमेशा स्ट्रिंग में आगे बढ़ रहे हैं, पिछले प्रतिस्थापन से मेल खाने वाले पैटर्न की कोई संभावना नहीं है।

यदि आप चरित्र (ब्रूट-फोर्स सर्च) द्वारा चरित्र खोज रहे हैं तो आपको यह पता लगाना होगा कि आप पैटर्न को प्राथमिकता देना चाहते हैं; लंबाई या क्रम से वे पैटर्न सूची में जोड़ा गया था।

अन्यथा, आप शब्द या वाक्य द्वारा वाक्य द्वारा शब्द खोज रहे होंगे जो एक बफर का उपयोग करके खोज में सामान्यीकृत होता है। इसके लिए आपको विभाजक निर्धारित करना होगा (शब्दों के लिए यह रिक्त स्थान होगा, वाक्यों के लिए यह विस्मयादिबोधक बिंदु और अन्य चीजों की तरह होगा, अल्पविराम से अलग मूल्य फ़ाइल के लिए यह अल्पविराम होगा)।