c++ merkkijonossa usean sanan korvaaminen vastaavilla arvoilaan

[teele]

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.




 

[kamara]

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/