Kirjoittaja Aihe: c++ merkkijonossa usean sanan korvaaminen vastaavilla arvoilaan  (Luettu 943 kertaa)

teele

  • Käyttäjä
  • Viestejä: 688
    • Profiili
Pitemmässä merkkijonossa on lyhyitä alimerkkijonoja, jotka haluttaisiin korvata niiden uusilla arvoilla.

aaa  aa x0x1  aaa x2   a x3 aaaaaaaaaaaaaa x4 .....

Kaikki x-arvot halutaan korvata uusilla arvooilla, jotka voivat olla vaikka suoraan vektoriista [y0, y2, y3 .... ] tai muulla tavalla tunnettuja niin, että jokaista x-arvoa pitäisi tulla korvaamaan tunnettu uusi y:n arvo

aaa  aa y0y1  aaa y2   a y3 aaaaaaaaaaaaaa y4 .....

Miten korvaus kannattaisi tehdä c++ :aa ja sen stl: ää käyttäen niin, että ei tekisi turhan raskasta proseduuria, O(n) tuntuisi mahdolliselta.




 
« Viimeksi muokattu: 29.01.22 - klo:10.07 kirjoittanut teele »

kamara

  • Käyttäjä
  • Viestejä: 2658
    • Profiili
https://fi.frwiki.wiki/wiki/Algorithme_de_Knuth-Morris-Pratt

Tästä varmaankin löytyy valmiiksi pureskeltuja vastauksia (siis valmiita koodinpätkiä), mutta sen avulla tosiaan ongleman voi hoitaa kaipaamallasi O(n):llä.

Säännölliset lausekkeet löytyy monista kielistä, jotka on käsittääkseni toteutettu tällä algoritmilla.

Edit - Tällainen algoritmi löytyi C-sukuiselle kielelle, en tosin ole tarkastanut, enkä kokeillut kyseistä koodia:
https://www.geeksforgeeks.org/finite-automata-algorithm-for-pattern-searching/
« Viimeksi muokattu: 29.01.22 - klo:10.24 kirjoittanut kamara »